Generating distinct random numbers

Dev Shed Forums Sponsor:

October 16th, 2011, 03:10 AM

leszek31417

Contributing User

Join Date: Jul 2011

Posts: 313

Time spent in forums: 1 Week 2 Days 18 h 56 m
Reputation Power: 0

Generating distinct random numbers

From time to time, I need an array of distinct, randomly chosen, positive integers.

One solution is below:

Code:

   int a[N];

   for ( i=0; i<N; i++ ) a[i] = i;

   for ( t=0; t<9999; t++ ) {
      i = rand()%N;
      j = rand()%N;
      help = a[i]; a[i] = a[j]; a[j] = help; // swap a[i] with a[j]
   }

Do you know something better ?

October 16th, 2011, 05:08 AM

LittleGrin

Contributing User

Join Date: Oct 2007

Posts: 921

Time spent in forums: 1 Week 11 h 50 m 18 sec
Reputation Power: 535

You don't need the second loop to go 9999 times. N times is enough. Only one random value per loop iteration is also enough.

For the shuffling, I'd probably use the technique which is (IIRC) employed in the C++ random_shuffle() algorithm.

Code:

    for (size_t i = 0; i < N; ++i) a[i] = i;
    for (size_t i = N-1; i > 0; --i)
    {
         size_t i_rand = rand() % N
         int help = a[i];
         a[i] = a[i_rand];
         a[i_rand] = help;
    }

__________________
Right 98% of the time, and don't care about the other 3%.

“It has been said that the great scientific disciplines are examples of giants standing on the shoulders of other giants. It has also been said that the software industry is an example of midgets standing on the toes of other midgets.” (Alan Cooper)

October 16th, 2011, 07:18 AM

leszek31417

Contributing User

Join Date: Jul 2011

Posts: 313

Time spent in forums: 1 Week 2 Days 18 h 56 m
Reputation Power: 0

I see !...

Swapping a[i] with random a[j].

That's better ...

Why backward loop ?

And (most important) why only N steps ?

...

Thank you!

October 16th, 2011, 07:59 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,458

Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 33 m 33 sec
Reputation Power: 403

gsl shuffle

gsl shuffle

The gsl random routines let you select from a good variety of prngs using the environment.

And why only one pass through the loop? Each number is given a chance to move to a different location.
SWAP(a[i -- known] , a[j---random] )
I also don't understand the "backward through the loop" business.

Without running it with print statements, it looks like a[0] is neglected.

Code:

    for (size_t i = 0; i < N; ++i) a[i] = i;
    for (size_t i = N; i-- > 0; )  /* this looks correct to me */
    {
         size_t i_rand = rand() % N
         int help = a[i];
         a[i] = a[i_rand];
         a[i_rand] = help;
    }

Also, and this is probably too much work, if all the bits of from the prng are good, and you need a small random integer, you can use R%N as your random number, and then take R/=N while R>N . I treat my random numbers as precious.

Last edited by b49P23TIvg : October 16th, 2011 at 08:03 PM. Reason: clarify

October 17th, 2011, 02:38 AM

leszek31417

Contributing User

Join Date: Jul 2011

Posts: 313

Time spent in forums: 1 Week 2 Days 18 h 56 m
Reputation Power: 0

Maybe like this :

Code:

   for ( i=0; i<N; i++ ) a[i] = i;

   for( i=N-1; i>0; i-- ){
 
      j = rand()%(i+1); // 0 <= j <= i
 
      h = a[i]; a[i] = a[j]; a[j] = h;  // swap a[i] with a[j]

   }

This explains counting down.
And there is no need for last step (when i=0).

...

Thank you for all remarks !

October 17th, 2011, 03:41 AM

LittleGrin

Contributing User

Join Date: Oct 2007

Posts: 921

Time spent in forums: 1 Week 11 h 50 m 18 sec
Reputation Power: 535

I just looked up the algorithm. I got it wrong - I was typing it in from memory, after all. The line

Code:

    size_t i_rand = rand() % N

should be

Code:

    size_t i_rand = rand() % (i + 1);

(I've added a missing semi-colon too). This is consistent with leszek's last post.

If you want a mathematical discussion of the reasoning, dig out Donald Knuth's "The Art of Computer Programming" - specifically the second volume entitled "Seminumerical Algorithms". It is discussed in Section 3.4.2 "Random Sampling and Shuffling" as "Algorithm P".

The results are uniformly distributed (i.e. all shuffled arrays are equally likely). If you really want to dig into the reasoning, Knuth gives references to the articles where the algorithm was first published.

When tweaking algorithms like this it is very easy to produce something that looks like a random shuffle but really is not. Iterating a few more times, for example, would change the distribution of results.

October 17th, 2011, 04:00 AM

leszek31417

Contributing User

Join Date: Jul 2011

Posts: 313

Time spent in forums: 1 Week 2 Days 18 h 56 m
Reputation Power: 0

Now, the algorithm models exactly the experiment of
selecting balls from an urn without replacement.

Thank you.

October 17th, 2011, 05:28 AM

mitakeet

I'm Baaaaaaack!

Dev Shed God 1st Plane (5500 - 5999 posts)

Join Date: Jul 2003

Location: Maryland

Posts: 5,538

Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 242

In my early days as a programmer I needed to do exactly this. I experimented with lots of ways to get it, but the swapping locations in an initially sorted array was the fastest and most reliable way I found.

__________________

My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
Free code: http://sol-biotech.com/code/.
Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
--Me, I just made it up

The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
--George Bernard Shaw

Generating distinct random numbers

Developer Shed Advertisers and Affiliates