如何从C ++向量中获取2个随机(不同)元素

本文介绍了如何从C ++向量中获取2个随机(不同)元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想从std :: vector获得2个随机的不同元素.我该怎么做才能做到:

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

• 速度快(在我的算法中完成了数千次)
• 优雅
• 元素选择实际上是均匀分布的

推荐答案

出于简洁的考虑:

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.

对于均匀性而言，这非常棘手，因为随着大小接近RAND_MAX，将偏向于较低的值，并且如果大小超过RAND_MAX，则将存在从未选择的元素.解决此问题的一种方法是使用二进制搜索:

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; }