0

I have a function that creates a vector of size N, and shuffles it:

void rand_vector_generator(int N) {
   srand(time(NULL));
   vector <int> perm(N);
   for (unsigned k=0; k<N; k++) {
      perm[k] = k;
   }
   random_shuffle(perm.begin(),perm.end());
}

I'm calling this from my main function with the loop:

for(int i=0; i<20; i++)
    rand_vector_generator(10);

I expected this to not give me sufficient randomness in my shuffling because I'm calling srand(time(NULL)); with every function call and the seed is not too different from successive call to call. My understanding is that I call srand(time(NULL)); once and not multiple times so the seed doesn't "reset".

This thread somewhat affirms what I was expecting the result to be.

Instead, I get:

6 0 3 5 7 8 4 1 2 9 
0 8 6 4 2 3 7 9 1 5 
8 2 4 9 5 0 6 7 1 3 
0 6 1 8 7 4 5 2 3 9 
2 5 1 0 3 7 6 4 8 9 
4 5 3 0 1 7 2 9 6 8 
8 5 2 9 7 0 6 3 4 1 
8 4 9 3 1 5 7 0 6 2 
3 7 6 0 9 8 2 4 1 5 
8 5 2 3 7 4 6 9 1 0 
5 4 0 1 2 6 8 7 3 9 
2 5 7 9 6 0 4 3 1 8 
5 8 3 7 0 2 1 6 9 4 
7 4 9 5 1 8 2 3 0 6 
1 9 2 3 8 6 0 7 5 4 
0 6 4 3 1 2 9 7 8 5 
9 3 8 4 7 5 1 6 0 2 
1 9 6 5 3 0 2 4 8 7 
7 5 1 8 9 3 4 0 2 6 
2 9 6 5 4 0 3 7 8 1

These vectors seem pretty randomly shuffled to me. What am I missing? Does the srand call somehow exist on a different scope than the function call so it doesn't get reset every call? Or am I misunderstanding something more fundamental here?

Community
  • 1
  • 1
Ritwik Biswas
  • 1,329
  • 1
  • 13
  • 18
  • 5
    `random_shuffle` doesn't necessarily call `rand`. – aschepler Apr 09 '17 at 00:28
  • The standard has definitely had a few goes at `random_shuffle` http://en.cppreference.com/w/cpp/algorithm/random_shuffle is (3) the only one valid in C++17 and later? – Richard Critten Apr 09 '17 at 00:39
  • 1
    How would you tell whether something has "sufficient randomness"? Did you run any statistical tests? – Kerrek SB Apr 09 '17 at 00:40
  • Calling `std::srand(std::time(0))` should simply give you the same seed within every second, it's still going to cause the random number generator to generate suitably random numbers. – Galik Apr 09 '17 at 00:40
  • Doesn't `std::random_shuffle` shuffles so each possible permutation has "equal" probability? You have to check how often each permutation occurs. Basically, for vector of two elements "1" and "2", "12" and "21" should appear 50% of the time each. – lapk Apr 09 '17 at 00:43

1 Answers1

3

According to standard the use of std::rand in both std::random_shuffle and std::shuffle is implementation-defined (though it is often the case that an std::rand is used this is not guaranteed). Try it on another compiler? Another platform?

If you want to make sure the std::rand is used you should let your code use it explicitly (for example, using lambda expression):

random_shuffle(perm.begin(), perm.end(), []{return std::rand();});

On a somewhat unrelated note, the time()'s precision is one whole second, your code runs way faster than that (I would hope) so those multiple calls to srand() result in resetting to the same-ish seed

YePhIcK
  • 5,816
  • 2
  • 27
  • 52
  • Std::rand does not have the correct signature to be the third argument of std::random_shuffle. – rici Apr 09 '17 at 01:29
  • You are correct. I should have said "pseudo-code" as that was just an illustration of how it should be done, not the actual implementation. – YePhIcK Apr 09 '17 at 01:41