5

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

我有std::vector一些未确定大小的独特元素。我想从此向量中获取 20 个唯一且随机的元素。“唯一”是指我不想多次获取同一个索引。目前我这样做的方式是调用std::random_shuffle. 但这需要我打乱整个向量（可能包含超过 1000 个元素）。我不介意改变向量（虽然我不想这样做，因为我不需要使用线程锁），但最重要的是我希望它高效。我不应该洗牌超过我需要的。

请注意，我已经考虑过将部分范围传递给，std::random_shuffle但它只会打乱该元素子集，这意味着该范围之外的元素永远不会被使用！

帮助表示赞赏。谢谢！

注意：我使用的是 Visual Studio 2005，因此无法访问 C++11 功能和库。

4

4 回答 4

8

您可以使用 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 是无偏的，因此每个排列都是同样可能的。该算法的现代版本也相当有效，只需要与被洗牌的项目数量成正比的时间，并且不需要额外的存储空间。费雪-耶茨洗牌的基本过程类似于从帽子中随机挑选编号的票，或从一副牌中随机挑选一张牌，直到没有更多的牌。

我认为这个伪代码应该可以工作（有可能出现一个错误或其他问题，所以请仔细检查它！）：

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]);
}
于 2012-12-07T23:13:22.240 回答
8

你想要一个来自 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]现在是随机样本。

于 2012-12-07T23:15:24.897 回答
3

使用循环将随机索引号放入 a并在达到 20std::set时停止。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);
    }
}

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

于 2012-12-07T23:11:39.783 回答
0 
#include <iostream>
#include <vector>
#include <algorithm>

template<int N>
struct NIntegers {
  int values[N];
};
template<int N, int Max, typename RandomGenerator>
NIntegers<N> MakeNRandomIntegers( RandomGenerator func ) {
  NIntegers<N> result;
  for(int i = 0; i < N; ++i)
  {
    result.values[i] = func( Max-i );
  }
  std::sort(&result.values[0], &result.values[0]+N);
  for(int i = 0; i < N; ++i)
  {
    result.values[i] += i;
  }
  return result;
};

使用示例：

// use a better one:
int BadRandomNumberGenerator(int Max) {
  return Max>4?4:Max/2;
}
int main() {
  NIntegers<100> result = MakeNRandomIntegers<100, 500>( BadRandomNumberGenerator );
  for (int i = 0; i < 100; ++i) {
    std::cout << i << ":" << result.values[i] << "\n";
  }
}

使每个数字 1 的最大值小于上一个。对它们进行排序，然后将每个值按其前面的整数个数递增。

模板的东西只是商业外观。

于 2012-12-07T23:21:15.137 回答