Thread: Generating a sequence of numbers in a random order

Code:

		my_start_pos = rand() % num_skiers + 1;
		
		// is this starting position already occupied? 

		if (startpos[my_start_pos] != 0) {

			// occupied, find me a new starting position

			do {
				my_start_pos = rand() % num_skiers + 1;
				if (startpos[my_start_pos] == 0) {
					found = 1;
				}
			} while (found !=1);
		}

You never set found to something OTHER than 1 in the code.

And I think you could imrpove that code by not duplicating the random number generation - you only really need to have that bit of code once.

--
Mats

From what I understand, some shuffling algorithms shuffle better than others (duh). citizen's sorting idea should work, but then it is inefficient (slower than linear time) compared to the Fisher-Yates shuffle, according to a certain online encyclopedia of debatable repute.

If you're looking for an easier or simpler way to do what you are already doing...

This:

Code:

my_start_pos = rand() % num_skiers + 1;

if (startpos[my_start_pos] != 0) {
   do {
      my_start_pos = rand() % num_skiers + 1;
      if (startpos[my_start_pos] == 0) {
         found = 1;
      }
   } while (found !=1);
}

Is equivalent to this:

Code:

do my_start_pos = rand() % num_skiers + 1;
while (startpos[my_start_pos] != 0);

There's no need to mess around with the 'found' flag. However, your randomized algorithm has a non-deterministic bound on runtime -- it could potentially run for a very long time if that last slot never gets chosen by the random number generator (although this is very unlikely).

You could do it a more deterministic way by filling the array with the skiers in order, and then doing a fixed number of random swaps. Pick two random positions in the array and swap them. Do this... lets say num_skiers*2 times and the array should be pretty darn randomized. And it runs in linear time thanks to our choice of running it num_skiers*2 times.

With a small number of skiers like you're using, you aren't going to see any performance impact from using the non-deterministic algorithm. However, up the max number of skiers to a million, and you'll find it grinds to a halt, while the deterministic method handles it just fine.

Here's a simple test program if you're interested. Set METHOD to 1 to use your original way; set it to 2 to use the swapping method I described. (You also might want to comment out the printing... a million skiers might take a while to print )

Code:

#include <stdio.h>
#include <time.h>

// Your original method
#define METHOD 1

// The swapping method
//#define METHOD 2

#define MAX_SKIERS 1000000

int starting_lineup[MAX_SKIERS+1];

int main(void)
{
   int i, num_skiers = 1000000;
   srand(time(NULL));

#if METHOD == 1

   int skier_pos;

   //For each skier, assign them a random position in the starting lineup
   for (i = 1; i <= num_skiers; i++) {
      do skier_pos = rand() % num_skiers + 1;
      while (starting_lineup[skier_pos] != 0);

      starting_lineup[skier_pos] = i;
   }

#elif METHOD == 2

   int pos1, pos2, temp;

   for (i = 0; i <= num_skiers; i++)
      starting_lineup[i] = i;
   
   for (i = 0; i < num_skiers*2; i++) {
      // Generate two random positions
      pos1 = rand() % num_skiers + 1;
      pos2 = rand() % num_skiers + 1;

      // Swap the skiers at the two positions
      temp = starting_lineup[pos1];
      starting_lineup[pos1] = starting_lineup[pos2];
      starting_lineup[pos2] = temp;
   }

#endif
	
   printf("Method %d\nThe starting lineup (first to last):\n", METHOD);
   for (i = 1; i <= num_skiers; i++)
      printf("%s%d", (i == 1 ? "" : ", "), starting_lineup[i]);
   putchar('\n');

   return 0;
}

Originally Posted by arpsmack

You could do it a more deterministic way by filling the array with the skiers in order, and then doing a fixed number of random swaps. Pick two random positions in the array and swap them. Do this... lets say num_skiers*2 times and the array should be pretty darn randomized. And it runs in linear time thanks to our choice of running it num_skiers*2 times.

From what I understand, the problem with that is that it introduces a bias unless you are careful (and your example implementations were not careful). The algorithm outlined in that online encyclopedia of debatable repute decreases the range of random numbers on each iteration of the loop.

EDIT:

Originally Posted by rasta_freak

Come on, it's only 48 skiers (integers). MAX. It's not the case for fancy-schmancy shuffles or Judy tries. It's simulation after all, so it's better to run this logic "random()%1000" times than go learn all this theory. First people should use common methods and only after they understand them and see their drawbacks, only then should they go looking for alternative/better solutions. Otherwise, it's just double confusion...

To some extent that is true: if a slight bias is of no consequence in this simulation, then it does not matter. On the other hand, I daresay that this is a good opportunity to learn a new and correct algorithm. That said, it is rather unfortunate that the C standard library lacks a random_shuffle algorithm to complement qsort() and rand().

And about random(), i don't know other people's experiences, but i find it more "random" the more i take values from it (calling random()). So, if you "draw" 100,000 values ranged from 1-100 (using &#37, you'll get proportional distribution of values, but if you take 1000, you may get some values few times (orders?) more often. So, with enough number of "drawing" back random values, he should get adequate distribution in this situation.

The quality of rand() varies with the implementation, since neither the C nor the C++ standard specifies an implementation for rand(). What you are referring to may be psychological, like seeing a run of heads when tossing a coin and believing there to be a bias where there is none, but of course this evens out in the long run. There is a slight bias when using modulo to reduce the range if the reduced range is not congruent to the range of the generator, but then again your point about such bias not being important here does stand.

Originally Posted by laserlight

The quality of rand() varies with the implementation, since neither the C nor the C++ standard specifies an implementation for rand(). What you are referring to may be psychological, like seeing a run of heads when tossing a coin and believing there to be a bias where there is none, but of course this evens out in the long run. There is a slight bias when using modulo to reduce the range if the reduced range is not congruent to the range of the generator, but then again your point about such bias not being important here does stand.

Well, actually i programmed few poker games. Now, i'm not saying they are something special, but here on local market, they "passed". So i faced this random() situation and made tests. Lots of tests. Even did my versions of random(). And best results i came up with were with standard GNU random() drawn 50-500 times per number. I even implemented "auto-play" in games, so we could test them for days/weeks, you get the picture. So when we compared statistics with different methods, it was easy to decide. But don't get me wrong - there are better methods, superior, faster. But in practice, plain random() can do miracles...

EDIT: about % reducing randomness, I read somewhere that GNU random() is "designed" in that way, that assumes using %, so no randomness is lost (it randomizes equaly all bits). But i can't confirm that, don't know source of that info...

EDIT: about % reducing randomness, I read somewhere that GNU random() is "designed" in that way, that assumes using %, so no randomness is lost (it randomizes equaly all bits). But i can't confirm that, don't know source of that info...

hmm... is that even possible? Like, if you are going to place 8 items as evenly as possible into 3 buckets, surely one bucket must have 2 items whereas the others have 3 items each.