How to get 2 random (different) elements from a c++ vector

Question

I would like to get 2 random different elements from an std::vector. How can I do this so that:

• It is fast (it is done thousands of times in my algorithm)
• It is elegant
• The elements selection is really uniformly distributed

Answer 1

For elegance and simplicty:

void Choose (const int size, int &first, int &second)
{
  // pick a random element
  first = rand () * size / MAX_RAND;
  // pick a random element from what's left (there is one fewer to choose from)...
  second = rand () * (size - 1) / MAX_RAND;
  // ...and adjust second choice to take into account the first choice
  if (second >= first)
  {
     ++second;
  }
}

using first and second to index the vector.

For uniformness, this is very tricky since as size approaches RAND_MAX there will be a bias towards the lower values and if size exceeds RAND_MAX then there will be elements that are never chosen. One solution to overcome this is to use a binary search:

int GetRand (int size)
{
  int lower = 0, upper = size;
  do
  {
    int mid = (lower + upper) / 2;

    if (rand () > RAND_MAX / 2) // not a great test, perhaps use parity of rand ()?
    {
       lower = mid;
    }
    else
    {
       upper = mid;
    }
  } while (upper != lower); // this is just to show the idea,
                            // need to cope with lower == mid and lower != upper
                            // and all the other edge conditions

  return lower;
}

Answer 2

What you need is to generate M uniformly distributed random numbers from [0, N) range, but there is one caveat here.

One needs to note that your statement of the problem is ambiguous. What is meant by the uniformly distributed selection? One thing is to say that each index has to be selected with equal probability (of M/N, of course). Another thing is to say that each two-index combination has to be selected with equal probability. These two are not the same. Which one did you have in mind?

If M is considerably smaller than N, the classic algorithm for selecting M numbers out of [0, N) range is Bob Floyd algorithm that can be found in Bentley's "Programming Peals" book. It looks as follows (a sketch)

for (int j = N - M; i < N; ++j) {

  int rand = random(0, j); // generate a random integer in range [0, j]

  if (`rand` has not been generated before)
    output rand;
  else
    output j;
}

In order to implement the check of whether rand has already been generated or not for relatively high M some kind of implementation of a set is necessary, but in your case M=2 it is straightforward and easy.

Note that this algorithm distributes the sets of M numbers uniformly. Also, this algorithm requires exactly M iterations (attempts) to generate M random numbers, i.e. it doesn't follow that flawed "trial-and-error" approach often used in various ad-hoc algorithms intended to solve the same problem.

Adapting the above to your specific situation, the correct algorithm will look as follows

first = random(0, N - 2);  
second = random(0, N - 1);
if (second == first)
  second = N - 1;

(I leave out the internal details of random(a, b) as an implementation detail).

It might not be immediately obvious why the above works correctly and produces a truly uniform distribution, but it really does :)

Answer 3

How about using a std::queue and doing std::random_shuffle on them. Then just pop til your hearts content?

Answer 4

Not elegant, but extreamly simple: just draw a random number in [0, vector.size()[ and check it's not twice the same.

Simplicity is also in some way elegance ;)

What do you call fast ? I guess this can be done thousands of times within a millisecond.