c++ - 如何生成升序随机整数列表

Question

我有一个包含 n 个元素的外部集合，我想随机选择其中的一些 (k) 个元素，将这些元素的索引输出到某个序列化数据文件。我希望索引按严格的升序输出，并且没有重复项。 n 和 k 都可能很大，简单地将整个数组存储在该大小的内存中通常是不可行的。

我想出的第一个算法是从 1 到 n-k 中选择一个随机数 r[0]... 然后从 r[i-1]+1 到 n- 中选择一个连续的随机数 r[i] k+i，一次只需要为'r'存储两个条目。然而，一个相当简单的分析表明，选择小数字的概率与整个集合均匀分布时的概率不一致。例如，如果 n 是十亿，k 是十亿分之一，那么使用我刚才描述的方法选择第一个条目的概率非常小(十亿分之一)，实际上，因为一半的条目是被选中时，第一个应该被选中的概率为 50%。即使我使用外部排序对 k 个随机数进行排序，我也必须丢弃所有重复项，然后重试。随着 k 接近 n，重试次数将继续增加，并且无法保证终止。

如果可能的话，我想找到一个 O(k) 或 O(k log k) 的算法来执行此操作。我将使用的实现语言是 C++11，但伪代码中的描述可能仍有帮助。

Answer 1

如果在实践中 k 与 n 具有相同的数量级，也许非常简单的 O(n) 算法就足够了:

assert(k <= n);
std::uniform_real_distribution rnd;
for (int i = 0; i < n; i++) {
    if (rnd(engine) * (n - i) < k) {
        std::cout << i << std::endl;
        k--;
    }
}

它以相等的概率生成所有升序序列。