Thread: using rand() to create a range of numbers

Say you need all the numbers between 1 and 26 in a random order (no repeats). What's the best way to go about doing that? I can think of some extremely inefficient ways...

Originally Posted by keira

Say you need all the numbers between 1 and 26 in a random order (no repeats). What's the best way to go about doing that? I can think of some extremely inefficient ways...

Fill an array with the values 1..26 and then "shuffle" it somehow. Try Googling for "random shuffle." It's easy to make a mistake and cause the shuffle to be not-quite-random, so be careful.

If it were me, I'd do the following:

Code:

int array[26] = { 0 }; /* Initialize array to all zeros */
int i;
int index;

for(i = 1; i <= 26; i++)
{
    do
    {
        index = rand() % 26; /* Random position between 0 and 25 */
    } while(array[index] > 0);
    array[index] = i;
}

Basically, this loops through all the values 1..26 and selects a random spot in the array to put that value. It uses the special value 0 to mean, "No value here." If there is already some other value at that spot, i.e., if there is a non-zero value at that index, it loops, trying random indexes until it finds an unfilled spot.

There are other ways, of course.

Thanks, I will look into shuffling.

P.S.

Your algorithm is flawed as it doesn't shield against repeat values returned by rand().

Originally Posted by keira

Your algorithm is flawed as it doesn't shield against repeat values returned by rand().

Yes it does.

In the C++ standard library there's actually a function random_shuffle() which is implemented using the following simple algorithm:

http://www.nist.gov/dads/HTML/fisherYatesShuffle.html

Edit: Also see

http://en.wikipedia.org/wiki/Shuffli...ing_algorithms

C board, not C++.

What you need is pseudo-random traversal of a set algo. This algo guarantees that every member of a set will be visited at random but will be visited exactly once.

Google it.

Originally Posted by prog-bman

C board, not C++.

The algorithm is what matters - I just mentioned that the C++ standard library uses it as evidence that it's worthy.