5

I need to generated random numbers in the range [0, 10] such that:

  • All numbers occur once.
  • No repeated results are achieved.

Can someone please guide me on which algorithm to use?

slashmais
  • 7,069
  • 9
  • 54
  • 80
  • 7
    Generate a [0, 10) sequence and shuffle it. – cnicutar Jul 03 '12 at 17:41
  • 3
    First, [what have you tried?](http://whathaveyoutried.com) Second, which is it, 0-10 or 1-10? – Carl Norum Jul 03 '12 at 17:41
  • Hi Carl, I have tried generating the sequence with rand() function, but couldn't achieve the result. Second, Range mentioned above is 0 to 10. Thanks –  Jul 03 '12 at 17:43
  • @billjoy For future reference, the numbers 0-10 in interval notation *inclusive* of 0 and 10 would be [0,10]. – Alex W Jul 03 '12 at 17:50
  • @billjoy What do you mean by _"no repeated results are achieved"_? – Eitan T Jul 03 '12 at 17:53

3 Answers3

11

The algorithm in Richard J. Ross's answer is incorrect. It generates n^n possible orderings instead of n!. This post on Jeff Atwood's blog illustrates the problem: http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html

Instead, you should use the Knuth-Fisher-Yates Shuffle:

int values[11] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
srand(time(NULL));

for (int i = 10; i > 0; i--)
{
    int n = rand() % (i + 1);

    int temp = values[n];
    values[n] = values[i];
    values[i] = temp;
}
japreiss
  • 11,111
  • 2
  • 40
  • 77
  • 1
    Is it the Knuth- or the Fisher-Yates-shuffle [http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle]? It is here as well: http://stackoverflow.com/questions/1150646/card-shuffling-in-c-sharp – slashmais Jul 03 '12 at 18:07
  • On the wikipedia-page it is aka Knuth-shuffle - I should have read the intro, not just skimmed to the details ;) – slashmais Jul 03 '12 at 18:11
  • It probably won't matter for this small of a dataset, but make sure that your system `rand` function is actually a good random number generator (or grab a standard one like the [Mersenne-Twister](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html). The `rand` call in some C libraries (hopefully only older ones) have well-known statistical problems (http://www.pnas.org/content/61/1/25.full.pdf+html). – sfstewman Jul 03 '12 at 18:37
  • Note that because `rand() % (i + 1)` will give biased numbers, this shuffle will be biased too. – caf Jul 04 '12 at 00:39
1

Try out this algorithm for pseudo-random numbers:

int values[11] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
srand(time(NULL));

for (int i = 0; i < 11; i++)
{
    int swap1idx = rand() % 11;
    int swap2idx = rand() % 11;

    int tmp = values[swap1idx];
    values[swap1idx] = values[swap2idx];
    values[swap2idx] = tmp;
}

// now you can iterate through the shuffled values array.

Note that this is subject to a modulo bias, but it should work for what you need.

Richard J. Ross III
  • 55,009
  • 24
  • 135
  • 201
0

Try to create a randomize function, like this:

void randomize(int v[], int size, int r_max) {
    int i,j,flag;

    v[0] = 0 + rand() % r_max; // start + rand() % end
    /* the following cycle manages, discarding it,
the case in which a number who has previously been extracted, is re-extracted. */
    for(i = 1; i < size; i++) {
        do {
            v[i]= 0 + rand() % r_max;
            for(j=0; j<i; j++) {
                if(v[j] == v[i]) {
                    flag=1;
                    break;
                }
                flag=0;
            }
        } while(flag == 1);
    }
}

Then, simply call it passing an array v[] of 11 elements, its size, and the upper range:

randomize(v, 11, 11);

The array, due to the fact that it is passed as argument by reference, will be randomized, with no repeats and with numbers occur once.

Remember to call srand(time(0)); before calling the randomize, and to initialize int v[11]={0,1,2,3,4,5,6,7,8,9,10};

A_nto2
  • 1,106
  • 7
  • 16