1

I have written the following piece of code to generate a random sequence of certain numbers {0,1,2,...,31}. It works fine, however, it cannot be guaranteed to complete within any finite amount of time; after any interval there is still only a certain (very high) probability that it will have completed. Any suggestion for removing this issue?

int th;
vector<int> V2 = vector<int> (32,0);
for (int k=0;k<32;k++){

    do{
        th = rand() % 32;
    } while ( V2[th] == 0 );

    V2[th] = k;
}
AJMansfield
  • 4,039
  • 3
  • 29
  • 50
ehsan moghadam
  • 149
  • 1
  • 7
  • Can you be more specific about what you mean by "non-deterministic time?" Also, WTF is that brace/indentation style you're using? – Robert Harvey Jun 19 '13 at 18:20
  • @RobertHarvey bounded over malicious values of `rand`, I figured. – djechlin Jun 19 '13 at 18:21
  • 2
    Isn't this an infinite loop? You create your vector and fill with value 0, then you have `while (V2[th]==0);`. You don't change any values before that loop, so `V2[th]==0` will always be true – wlyles Jun 19 '13 at 18:24
  • 1
    Now that's a creative way to create a permutation. This is really bad code, and shouldn't be used in real world applications. But +1 for the idea... @wlyles: it actually works (at least in most cases) – Axel Jun 19 '13 at 18:25
  • Regardless of whether this is an infinite loop, I think I understand what the principle is. It runs in non-deterministic time because of how you select your random index. You always pick from between 0 and 31 for `th`, so there is no telling how many iterations of the `do while` loop will execute before you find an index with non-zero value, especially once most of the values are non-zero (in other words, as `k` gets bigger) – wlyles Jun 19 '13 at 18:33

2 Answers2

7

And an actual implementation:

int a[] = { 0, 1, 2, ....., 31 };
std::random_shuffle(a, a + 32);

or with vectors:

std::vector<int> v(a, a + 32); // from previous snippet
std::random_shuffle(v.begin(), v.end());

In addition, as usually, don't forget to seed the PRNG if you want true-ish random permutations.

  • If he wants to use `vector V2`, then `std::random_shuffle(V2.begin(), V2.end());` would be more appropriate – wlyles Jun 19 '13 at 18:26
3

Populate a vector with the numbers between zero and 31, and then use a linear-time random shuffle algorithm, such as Fisher-Yates.

NPE
  • 486,780
  • 108
  • 951
  • 1,012