Processing 1.0 - Processing Discourse

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Programs › arrays and random

‹ Previous Topic | Next Topic ›

Pages: 1

arrays and random (Read 1747 times)

Danno2106

arrays and random
May 7^th, 2010, 8:02pm

Im trying to fill an array with random numbers that do not repeat, I am able to creat an array that is random but repeats, or an array that does nothing but fill with the same number, i am trying to use a do while loop.

Code:


int[] myArray = new int[16];

  boolean isNotInArray = true; 
  int x = 0;
  int num = int(random(16));
      do
 
      {
     
       for( int i=0; i < 16; i++ )
 
      {
  
      if( num == myArray[i] )
   
      {
    exit();
      isNotInArray = false;
  
        
      }
            
 
      }
  
      }

      while( !isNotInArray );
      while(x < 16){
      myArray[x] = num;
      x++;
      }
      println(myArray);

The array only fills with one number.

Smitty

Re: arrays and random
Reply #1 - May 7^th, 2010, 8:41pm

If your code is formatted a little more neatly I think the answer becomes pretty obvious (comments are mine):

Code:


int[] myArray = new int[16];

boolean isNotInArray = true; 
int x = 0;
int num = int(random(16));

// We've now generated a random number.

do {
  for( int i=0; i < 16; i++ ) {
    if( num == myArray[i] ) {
      isNotInArray = false;
    }
  }
} while( !isNotInArray );

// We've now checked once to see if the number was already in the 
// array.  It wasn't, because the array is still empty.

while(x < 16){
  myArray[x] = num;
  x++;
}

// And now we've filled the array with the number.

println(myArray);

To fix the problem, you'll want to nest the do..while loop (checking for a repeat) in the while loop that cycles through the array elements, so that you're checking for repeats for each array element.

PhiLho

Re: arrays and random
Reply #2 - May 8^th, 2010, 12:34am

You want to fill an array of 16 slots with 16 different random numbers.
Doing that by redrawing a number if it is already in the list might be too long at the end...
The algorithm is fine if the range of random numbers is much bigger than the number of available slots. But then use break; to go out of the loop early, not exit(), and put it after the assignment!
In your case, it is called a shuffle, like when you mix cards.
This is usually done by swapping entries randomly.
See Fisher–Yates shuffle article.

Smitty

Re: arrays and random
Reply #3 - May 8^th, 2010, 7:54am

I think Danno's algorithm (once the bugs are fixed) should take O(n^2) time to fill all the elements in the array. Not great for large values of n, but for n=16 it should be manageable.

Something like this should work:
Code:


int[] myArray = new int[16];

for (int i = 0; i < 16; ++i) {
    int num;
    boolean isUnique = false;
    while (!isUnique) {
	  num = random(16);
	  isUnique = true;
	  for (int j = 0; j < i; ++j) {
		if (num==myArray[j]) {
		    isUnique = false;
		}
	  }
    }
    myArray[i] = num;
}

A simple shuffling algorithm (like what PhiLho suggests) would look like:

Code:


int[] myArray = new int[16];

// Start by filling the array in order:

for (int i = 0; i < 16; ++i) {
    myArray[i] = i;
}

// Then do some number of shuffles; I've chosen 100 here but you 
// could do more or fewer; whatever gives you "enough" randomness.

for (int i = 0; i < 100; ++i) {
    int j = random(16);
    int k = random(16);
    int temp = myArray[j];
    myArray[j] = myArray[k];
    myArray[k] = temp;
}

That's simpler code, and probably faster than the first way (although maybe not by enough to make a difference for your application.)

Danno2106 YaBB Newbies Offline Posts: 2	Re: arrays and random Reply #4 - May 8^th, 2010, 4:13pm Well I see that it works, the only problem is I dont know why it does work. I see that we fill the array in order, then notice we create two random numbers(from 0 - 16 in this case) and then have them swap. then we do this many times. Would this be a correct assumption?

PhiLho YaBB Moderator Offline Posts: 4190 Near Paris (France)	Re: arrays and random Reply #5 - May 9^th, 2010, 12:38am Yes, and if you look at the article I point to, you will find an optimal algorithm needing a minimal number of swaps.

blindfish

Re: arrays and random
Reply #6 - May 9^th, 2010, 2:34am

Smitty wrote on May 8^th, 2010, 7:54am:

That's simpler code, and probably faster than the first way (although maybe not by enough to make a difference for your application.)

Surely the issue with the while loop is that the timing isn't going to be consistent - one set of randomly generated values might re-order the numbers much more quickly than another. Whether this is noticeable to the end user is perhaps questionable; but I'd much rather use the consistent method; and prefer to avoid while loops that don't have a quantifiable end point unless absolutely necessary.

@Danno2106
Yep - I think that's a fair assumption. As an analogy the first approach (with the while loop) is equivalent to rolling a 16 sided dice and recording each new unique number until you have all 16 numbers. The second approach is like taking 16 numbered cards and shuffling them... I think that also sums up the advantage of the latter approach.

Where is the what if the what is in why?

Pages: 1

‹ Previous Topic | Next Topic ›