Generating a sequence of numbers in a random order

This is a discussion on Generating a sequence of numbers in a random order within the C Programming forums, part of the General Programming Boards category; Hi, I'm taking a university class in programming and I'm very new to C. C is my first programming language. ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Location
    Karlstad, Sweden
    Posts
    1

    Question 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!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    And if max. number of skiers is 47, and you start indexing from 1, you need "startpos[48]"...

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    66
    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.

  5. #5
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,660
    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.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    If you're looking for an easier or simpler way to do what you are already doing...

    This:
    Code:
    my_start_pos = rand() &#37; 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;
    }
    Last edited by arpsmack; 08-12-2008 at 11:44 AM.

  8. #8
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by laserlight View Post
    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...

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    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()&#37;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().
    Last edited by laserlight; 08-12-2008 at 11:55 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,660
    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.

  11. #11
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by laserlight View Post
    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.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by laserlight View Post
    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 &#37; 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...
    Last edited by rasta_freak; 08-12-2008 at 12:43 PM.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    EDIT: about &#37; 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by laserlight View Post
    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 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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generating Random Numbers
    By Flakster in forum C++ Programming
    Replies: 14
    Last Post: 08-22-2005, 12:50 PM
  2. Generate random numbers in Lucky7 project using C#
    By Grayson_Peddie in forum C# Programming
    Replies: 1
    Last Post: 04-11-2003, 11:03 PM
  3. programming with random numbers
    By xstudent in forum C Programming
    Replies: 13
    Last Post: 05-21-2002, 01:36 AM
  4. Generating Random Numbers
    By knight543 in forum C++ Programming
    Replies: 3
    Last Post: 01-11-2002, 05:55 PM
  5. arranging randomly generated numbers in ascending order
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-05-2001, 06:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21