如何从向量中获取随机和唯一值？

Question

可能重复:
O(1)中的唯一随机数？
C编程语言中整数数组中的唯一随机数

我有std::vector一些不确定大小的独特元素.我想从这个向量中获取20个唯一且随机的元素."独特"我的意思是我不想多次获取相同的索引.目前,我这样做是为了打电话std::random_shuffle.但这需要我将整个矢量(可能包含1000多个元素)混洗.我不介意改变向量(我不喜欢,因为我不需要使用线程锁),但最重要的是我希望它有效.我不应该比我需要的更多地洗牌.

请注意,我已经考虑过传入一个部分范围,std::random_shuffle但它只会洗掉那个元素子集,这意味着该范围之外的元素永远不会被使用!

感谢帮助.谢谢!

注意:我使用的是Visual Studio 2005,因此我无法访问C++ 11的功能和库.

Answer 1

您可以使用Fisher Yates http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Fisher-Yates shuffle(以Ronald Fisher和Frank Yates命名),也称为Knuth shuffle(在Donald Knuth之后),是一种用于生成有限集合的随机置换的算法,用于随机改组该集合.Fisher-Yates shuffle的变体(称为Sattolo算法)可用于生成长度为n的随机循环.正确实施,Fisher-Yates shuffle是公正的,因此每个排列都是同样可能的.该算法的现代版本也相当有效,只需要与被洗牌的项目数量成比例的时间,而不需要额外的存储空间.Fisher-Yates改组的基本过程类似于从帽子中随机挑选编号的门票,或从甲板上随意挑选卡片,直到不再剩下.具体算法提供的是一种以有效和严格的方式在数字上进行此操作的方法,正确完成后,保证了无偏的结果.

我认为这个伪代码应该可以工作(有可能出现一个错误或者其他东西,所以请仔细检查它!):

std::list chosen; // you don't have to use this since the chosen ones will be in the back of the vector
for(int i = 0; i < num; ++i) {
  int index = rand_between(0, vec.size() - i - 1);
  chosen.push_back(vec[index]);
  swap(vec[index], vec[vec.size() - i - 1]);
}

Answer 2

您想从n向量中随机抽取大小为m的样本:

让rand(a)返回0..a-1制服

for (int i = 0; i < m; i++)
    swap(X[i],X[i+rand(n-i)]);

X[0..m-1] 现在是随机样本.

Answer 3

使用循环将随机索引号放入 a 中std::set，并在达到 20 时停止size()。

std::set<int> indexes;
std::vector<my_vector::value_type> choices;
int max_index = my_vector.size();
while (indexes.size() < min(20, max_index))
{
    int random_index = rand() % max_index;
    if (indexes.find(random_index) == indexes.end())
    {
        choices.push_back(my_vector[random_index]);
        indexes.insert(random_index);
    }
}

随机数生成是我脑海中浮现的第一件事，请随意使用更好的东西。