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

Question

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

• It is fast (it is done thousands of times in my algorithm)
• Elegantly
• The selection of items is really evenly distributed.

Answer 1

For elegance and simplicity:

void Choose (const int size, int &first, int &second) { // pick a random element first = rand () * size / MAX_RAND; // pick a random element from what 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 the first and second to index the vector.

For uniformity, this is very difficult, since the size approaches RAND_MAX, there will be an offset to lower values, and if the size exceeds RAND_MAX, then there will be elements that will never be selected. One solution to overcome this is to use 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

You need to create M evenly distributed random numbers from the range [0, N), but there is one caveat here.

It should be noted that your statement of the problem is ambiguous. What is meant by a uniformly distributed choice? It is one thing to say that each index should be chosen with equal probability (of course, M / N). Another thing is that each combination with two indices should be chosen with equal probability. These two do not match. Which one did you mean?

If M is much smaller than N, the classic algorithm for choosing M numbers from the range [0, N) is Bob Floyd's algorithm, which can be found in Bentley’s book Pils Programming. It looks like this (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; } 

To implement a check that rand already generated or not for a relatively high M, some set implementation is required, but in your case, M = 2 is simple and simple.

Note that this algorithm distributes the sets of numbers M uniformly. In addition, this algorithm requires exactly M iterations (attempts) to generate M random numbers, i.e. It does not follow that the erroneous trial-and-error approach is often used in various ad-hoc algorithms designed to solve the same problem.

Applying the above to your specific situation, the correct algorithm will look like this

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

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

It cannot be immediately seen why this works correctly and creates a truly uniform distribution, but it really :)

Answer 3

How about using std::queue and executing std::random_shuffle on them. Then just popped your content?

Answer 4

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

Simplicity is also a bit of an elegance;)

How fast? I think it can be done thousands of times in a millisecond.

Answer 5

Whenever you need something random, you will have different questions about the properties of random numbers regarding uniformity, distribution, etc.

Assuming you have found a suitable source of randomness for your application, the easiest way to create pairs of uncorrelated records is to simply select two random indexes and check that they are not equal.

Given a vector of N + 1 entries, another option is to create an index i in the range 0..N. item [i] is selectable. Swap elements i and N. Create index j in the range 0 .. (N-1). the [j] element is your second choice. This slowly moves your vector, which may be problematic, but can be avoided by using a second vector that contains the indices in the first and shuffles it. This method handles a swap to compare indices and is generally more efficient for small vectors (for example, from a dozen or fewer elements), since it avoids the need to perform multiple comparisons as the number of collisions increases.

Answer 6

You can look at the gnu science library . It has pretty pretty random number generators that are guaranteed to be random to the bit level.