我想要一组从 {1,2,...(k-1),K} 中随机选择的 N 个不同数字，其中 K>N。我想编写一个 C 程序来有效地做到这一点。
任何帮助表示赞赏。
笔记：
天真的程序只是生成随机数，检查它是否已经生成，如果没有将其添加到列表中，则很容易实现。我一直在寻找更有效的东西，好像 K 和 N 是可比的，那么这将只是低效的计算。
问问题
1140 次
2 回答
3
当 K 和 N 具有可比性时，使用Knuth shuffle，但将 shuffle 限制为仅 N 次。
请注意，当它们不是时，这可能会浪费大量内存。
于 2013-04-29T13:24:58.947 回答
2
“<a href="http://en.wikipedia.org/wiki/Reservoir_sampling" rel="nofollow">水库抽样是一系列随机算法，用于从包含 n 个项目的列表 S 中随机选择 k 个样本，其中 n 是一个非常大或未知的数字。”</p>
（请注意，关于您的问题，该维基百科页面上 K 和 N 的角色是相反的）
于 2013-04-29T13:25:35.450 回答