从 [0:n) 均匀采样 k 个整数
Uniform sampling of k integers from [0:n)
我的目标是从 0, ... n-1 中采样 k 个整数而不重复。采样整数的顺序无关紧要。在每次调用时（经常发生），n 和 k 会略有不同但不会太大（n 约为 250,000，k 约为 2,000）。我提出了以下分摊 O(k) 算法：
- 准备一个包含项目 0、1、2、...、n-1 的数组 A。这需要 O(n)，但由于 n 相对稳定，成本可以摊销为常量。
- 从 [0:i] 中抽取一个随机数 r，其中 i = n - 1。这里的成本实际上与 n 有关，但由于 n 不是很大，因此这种依赖性并不重要。
- 交换数组A中的第r项和第i项。
- 将 i 减 1。
- 重复步骤2~4 k次；现在我们在 A 的尾部有一个长度为 k 的随机排列。复制这个。
- 我们应该将 A 回滚到其初始状态 (0, ... , n-1) 以保持步骤 1 的成本不变。这可以通过在步骤 2 的每次传递时将 r 推入长度为 k 的堆栈来完成。堆栈的准备需要摊销的常数成本。
我认为 permutation/combination 的均匀采样应该是一个详尽研究的问题，所以要么 (1) 有更好的解决方案，要么至少 (2) 我的解决方案是众所周知的解决方案。因此，
- 在情况 (1) 中，我想知道更好的解决方案。
- 情况(2)，我要找参考
请帮助我。谢谢。
如果 k 远小于 n——比如说，小于 n 的一半——那么最有效的解决方案是保留数字在散列 table 中生成（实际上是一个散列集，因为没有与键关联的值）。如果随机数恰好已经在散列 table 中，则拒绝它并在其位置生成另一个随机数。根据建议的 k 和 n 的实际值 (k ∼ 2000; n ∼ 250,000)，生成 k 唯一样本的预期拒绝数小于 10，因此几乎不会引起注意。 hash的大小table为O(k)，可以在样本生成结束时简单删除
也可以使用散列 table 而不是 n 值的向量来模拟 FYK 洗牌算法，从而避免不得不拒绝生成的随机数。如果您使用的是向量 A，您将首先为每个 0 ≤ i < k 将 A[i] 初始化为 i。对于散列 table H，您从一个空散列 table 开始，并使用约定 H[i] 被认为是 i 如果键 i 不在散列 table 中。算法中的第 3 步 -- "swap A[r] with A[i]" -- 变为 "add H[r] as the next element of the sample and set H[r] to H[i]"。请注意，不必设置 H[i]，因为该元素将永远不会再次被引用：所有后续随机数 r 都是从不包括 i.[=50= 的范围内生成的]
因为本例中的散列 table 包含键和值，它比上面备选方案 1 中使用的散列集大，增加的大小（以及随之而来的内存缓存未命中数增加）是可能会导致比消除拒绝所节省的更多的开销。但是，它的优点是即使 k 偶尔接近 n.
最后，在你提出的算法中，在O(k)时间内恢复A其实是相当容易的。只有在以下情况下，算法才会修改值 A[j]：
一个。 n − k ≤ j < n，或
b。有一些 i 这样 n − k ≤ i < n 和 A[i] = j.
因此，您可以通过查看 n − k ≤ i < n 的每个 A[i] 来恢复向量 A：首先，如果 A[i] < n−k，将 A[A[i]] 设置为 A[i];然后无条件设置A[i]为i.
我的目标是从 0, ... n-1 中采样 k 个整数而不重复。采样整数的顺序无关紧要。在每次调用时（经常发生），n 和 k 会略有不同但不会太大（n 约为 250,000，k 约为 2,000）。我提出了以下分摊 O(k) 算法：
- 准备一个包含项目 0、1、2、...、n-1 的数组 A。这需要 O(n)，但由于 n 相对稳定，成本可以摊销为常量。
- 从 [0:i] 中抽取一个随机数 r，其中 i = n - 1。这里的成本实际上与 n 有关，但由于 n 不是很大，因此这种依赖性并不重要。
- 交换数组A中的第r项和第i项。
- 将 i 减 1。
- 重复步骤2~4 k次；现在我们在 A 的尾部有一个长度为 k 的随机排列。复制这个。
- 我们应该将 A 回滚到其初始状态 (0, ... , n-1) 以保持步骤 1 的成本不变。这可以通过在步骤 2 的每次传递时将 r 推入长度为 k 的堆栈来完成。堆栈的准备需要摊销的常数成本。
我认为 permutation/combination 的均匀采样应该是一个详尽研究的问题，所以要么 (1) 有更好的解决方案，要么至少 (2) 我的解决方案是众所周知的解决方案。因此，
- 在情况 (1) 中，我想知道更好的解决方案。
- 情况(2)，我要找参考
请帮助我。谢谢。
如果
k远小于n——比如说，小于n的一半——那么最有效的解决方案是保留数字在散列 table 中生成（实际上是一个散列集，因为没有与键关联的值）。如果随机数恰好已经在散列 table 中，则拒绝它并在其位置生成另一个随机数。根据建议的k和n的实际值 (k ∼ 2000; n ∼ 250,000)，生成k唯一样本的预期拒绝数小于 10，因此几乎不会引起注意。 hash的大小table为O(k)，可以在样本生成结束时简单删除也可以使用散列 table 而不是
n值的向量来模拟 FYK 洗牌算法，从而避免不得不拒绝生成的随机数。如果您使用的是向量A，您将首先为每个0 ≤ i < k将A[i]初始化为i。对于散列 tableH，您从一个空散列 table 开始，并使用约定H[i]被认为是i如果键i不在散列 table 中。算法中的第 3 步 -- "swapA[r]withA[i]" -- 变为 "addH[r]as the next element of the sample and setH[r]toH[i]"。请注意，不必设置H[i]，因为该元素将永远不会再次被引用：所有后续随机数r都是从不包括i.[=50= 的范围内生成的]因为本例中的散列 table 包含键和值，它比上面备选方案 1 中使用的散列集大，增加的大小（以及随之而来的内存缓存未命中数增加）是可能会导致比消除拒绝所节省的更多的开销。但是，它的优点是即使
k偶尔接近n. 也能正常工作
最后，在你提出的算法中，在O(k)时间内恢复
A其实是相当容易的。只有在以下情况下，算法才会修改值A[j]：一个。
n − k ≤ j < n，或b。有一些
i这样n − k ≤ i < n和A[i] = j.因此，您可以通过查看
n − k ≤ i < n的每个A[i]来恢复向量A：首先，如果A[i] < n−k，将A[A[i]]设置为A[i];然后无条件设置A[i]为i.