如何从C++矢量中获得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;
}

您需要的是从[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个随机数,即它不遵循各种用于解决同一问题的特殊算法中经常使用的有缺陷的“试错”方法。

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

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

(我遗漏了 random(a, b) 作为实现细节)。

这可能不是显而易见的,为什么上面的工作是正确的,并产生一个真正的均匀分布,但它确实是这样的:)

用一个怎么样 std::queue 做 std::random_shuffle 在他们身上。那就跳到心满意足为止?

不优雅,但很简单:只需在[0,vector.size()]中绘制一个随机数,并检查它是否是相同的两倍。

简单在某种程度上也是优雅的;)

你叫什么快?我想这可以在一毫秒内完成数千次。

每当需要随机的东西时,你会有关于随机数属性的各种问题,关于均匀性、分布等等。

假设您已经为应用程序找到了一个合适的随机性来源,那么生成不相关项对的最简单方法就是选择两个随机索引并测试它们以确保它们不相等。

如果向量为n+1个条目,另一个选项是生成范围为0..n的索引i。元素[i]是选项1。交换元素i和n。生成范围为0..(n-1)的索引j。元素[J]是您的第二选择。这会慢慢地改变向量,这可能有问题,但是可以通过使用第二个向量将索引保存到第一个向量中,并改变它来避免。这种方法交换索引比较,对于小向量(通常为十几个或更少的元素)更有效,因为它避免了随着冲突次数的增加而进行多次比较。

你可能想看看 gnu scientific library . 这里有一些非常好的随机数生成器,保证是随机下降到位级别的。