paperjam - 1 year ago 83

C++ Question

What is a good way to get a [pseudo-]random element from an STL range?

The best I can come up with is to do

`std::random_shuffle(c.begin(), c.end())`

`c.begin()`

However, I might want a random element from a

`const`

Is there a better way?

Answer Source

All the answers using `%`

here are incorrect, since `rand() % n`

will produce biased results: imagine `RAND_MAX == 5`

and the number of elements is 4. Then you'll get twice more the number 0 and 1 than the numbers 2 or 3.

A correct way to do this is:

```
template <typename I>
I random_element(I begin, I end)
{
const unsigned long n = std::distance(begin, end);
const unsigned long divisor = (RAND_MAX + 1) / n;
unsigned long k;
do { k = std::rand() / divisor; } while (k >= n);
std::advance(begin, k);
return begin;
}
```

Another problem is that `std::rand`

is only assumed to have 15 random bits, but we'll forget about this here.