How to make sure that std::random_shuffle always produces a different result?

Question

Is there some function, similar to srand(), that I need to call to make sure that std::random_shuffle() always produces different results? i.e. if I call it several times with the same data, I want the order to be different every time. How can I make sure of that?

Bespatter

That doesn't sound very random to me... – Romaine

@Blindy: It's random, but the results are not uniformly distributed. – Raspy

srand is quite good. If it is not good enough for your need, search for other random generators (maybe boost) – Eparch

Make sure you NEVER call srand() more than once in a program. – Heliport

srand() doesn't make sure anything produces different results. @John: it's less and less random each time, because it's more and more predictable each time. – Divalent

@LokiAstari there are plenty of reasons to. If you care about running a MC algorithm multiple times with different parameters but the same random number stream, for example. – Kopple

Answer 1

std::random_shuffle has two forms. One that takes 2 arguments (begin/end iterators), and one that takes 3 (begin/end iterator and a random generator).

The first form uses std::rand(), so you would use std::srand() to seed it's random number generator. You can also use the 3-argument version and provide the RNG yourself.

Triolein

As I understand it, how the first form implements it is its business. Some platforms may not use std::rand. – Clyve

You're right. I was looking at the libstdc++ version. The original author should consult the documentation for your STL. Or if they don't want to rely on that, they should use the 3rd form and use something like boost::random or the C++0x std::random. – Triolein

Answer 2

std::random_shuffle has a template overload for specifying the RNG.

template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                        RandomNumberGenerator& rand );

reference

Clyve

Answer 3

random_shuffle is deprecated since C++14 (removed in C++17) and replaced with shuffle (exists since C++11) http://en.cppreference.com/w/cpp/algorithm/random_shuffle

possible usage:

shuffle(items.begin(), items.end(), std::default_random_engine(std::random_device()()));

Lunnete

Answer 4

I think you can give a random generator functor to std::random_shuffle, so you can be able to fully control the random number generation. Looking here, this functor takes the place of the RandomNumberGenerator template argument.

Geoid

Answer 5

Generally call srand(time(NULL)) before calling std::random_shuffle() would give you what you need, it give you different result each time you call std::random_shuffle(). It's because std::random_shuffle() internally calls rand() in many popular implementations (e.g. VS-2008 and GCC).

Of course you can supple a RNG yourself if you want to call the other overloaded std::random_shuffle with a extra parameter.

Killdeer

Answer 6

As a last resort, you can:

• Call std::random_shuffle
• Compute a hash of the sequence, store it in a std::set
• Discard if the hash is already present

I fail to see how using a custom generator could guarantee that the sequence is unique.

Norval