Generating a sequence of numbers in a random order

Hi, I'm taking a university class in programming and I'm very new to C. C is my first programming language.

My current assignment is to generate a certain amount of numbers in sequence (i.e. 1-40 or 1-15 etc.) and then present them in random order in an array. Duplicates are NOT allowed.

The numbers are later to be used as starting numbers for athletes in a fictional skiing competition (maximum number of skiers are 47).

My code is working so so, but not all numbers are assigned to an athlete and I also get some skiers assigned with starting number 0 (zero is obviously not allowed as starting number).

Code:

---


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

int main(void)
{
        int i, skier, random, num_skiers=10, found, startpos[46], pos, my_start_pos;

        srand(time(NULL));
               
        // empty the array

        for (i = 1; i <=num_skiers; i++) {
                startpos[i] = 0;
        }
       
        // go through the skiers

        for (skier = 1; skier <=num_skiers; skier++) {

                //generate a starting number for the skier

                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);
                }

                // assign this starting number to the skier

                startpos[my_start_pos] = skier;
        }
       
        for (pos = 1; pos <=num_skiers; pos++) {
                printf("Starting position %d is assigned to skier no. %d\n", pos, startpos[pos]);
        }

  return 0;
}

---

I bet there is easier way to do this and I'm open to everything, I just want to get past this obstacle :)

Any help is greatly appreciated!

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

And if max. number of skiers is 47, and you start indexing from 1, you need "startpos[48]"...

Code:

---

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

Hope this helps.

---

Well if you're lazy like me, then you'd simply assign each skier a position id and a random number, then use a sorting algorithm, like C's qsort, sorting by the random number. This creates a shuffle.

It would be a wonderful time to use a structure for the skiers.

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;
}

---

Quote:

---

Originally Posted by laserlight

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.

---

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...

Quote:

---

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:

Quote:

---

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().

Well 47 skiers is such a small period, you'd have a hard time not introducing bias I would think, unless you implemented your own PRNG, or shuffled using an external method like I did. It has its modest advantages: The thing with Fisher-Yates that I typically despised was the fact that I had to munge the random number to fit in the bounds of the array all the time.

Quote:

---

Originally Posted by laserlight

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().

---

Yes, that's unfortunate for me too. 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 %), 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.

Quote:

---

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 %), 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.

Quote:

---

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...

Quote:

---

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.

Quote:

---

Originally Posted by laserlight

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.

---

Sorry, i mistyped, or subtyped ;). I meant, if you draw random() "n" times, all bits should "toggle" proportional number of times. Now, when exactly this becomes visible (at which "n"), well, that's pretty random :D It can be after 10 draws, or after 10000, but there must be some built-in "limit" when full "cycle" is reached, and i don't know it.

I now that my previous post is pretty wrong, but point is that this randomizing of bits is combined with random value.

EDIT: I know where i read about it! It was either in man pages or linux howtos, where they talked about using high word and low word in 'ancient' times, and that with "new" random() they don't have to anymore. It was few years ago.

EDIT2: from "man 3 srand":
'However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits'.

So, if he's on windows, he could fall into "much less (random)" category...