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

Question

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

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

Answer 1

你需要的是从[0,N]范围生成M个均匀分布的随机数,但这里有一个警告.

需要注意的是,您对问题的陈述含糊不清.均匀分布的选择是什么意思？有一点是说必须以相同的概率选择每个指数(当然是M/N).另一件事是说必须以相同的概率选择每个双指数组合.这两个不一样.你记得哪一个？

如果M远小于N,则用于从[0,N]范围中选择M个数字的经典算法是Bob Floyd算法,该算法可以在Bentley的"Programming Peals"一书中找到.它看起来如下(草图)

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

为了实现rand对相对较高的M 是否已经生成的检查,有必要对某个集合进行某种实现,但在你的情况下M = 2它是简单易行的.

注意,该算法均匀地分配M个集合.此外,该算法需要恰好M次迭代(尝试)来生成M个随机数,即它不遵循通常用于解决相同问题的各种ad-hoc算法中的有缺陷的"试错法".

根据您的具体情况调整以上内容,正确的算法如下所示

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

(我省略了random(a, b)作为实现细节的内部细节).

为什么上面的工作正常并产生真正统一的分布可能不是很明显,但它确实:)

Answer 2

优雅和简洁:

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

使用第一个和第二个来索引向量.

为了统一性,这非常棘手,因为当尺寸接近RAND_MAX时,将偏向较低的值,如果尺寸超过RAND_MAX,则将存在从未选择的元素.解决此问题的一种解决方案是使用二进制搜索:

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 3

如何使用std::queue和执行std::random_shuffle它们.然后只是弹出你的心脏内容？