如何从C ++向量中获取2个随机(不同)元素 [英] How to get 2 random (different) elements from a c++ vector

问题描述

我想从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;
}

这篇关于如何从C ++向量中获取2个随机(不同)元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！