随机选择一组不同的整数的最有效的方法 [英] Most efficient way of randomly choosing a set of distinct integers
问题描述
我在寻找最有效的算法随机选择一组n个不同的整数，其中所有的整数是在一定范围内[0..maxValue。
I'm looking for the most efficient algorithm to randomly choose a set of n distinct integers, where all the integers are in some range [0..maxValue].
约束：
- 包括maxValue是大于n，并且可能大得多
- 在我不在乎，如果输出列表进行排序或不
- 在所有整数必须以相同的概率选择
我最初的想法是构建整数[0..maxValue]然后提取n个元素的列表，随机无需更换。但是，这似乎很低效的，特别是如果包括maxValue是很大的。
My initial idea was to construct a list of the integers [0..maxValue] then extract n elements at random without replacement. But that seems quite inefficient, especially if maxValue is large.
没有更好的办法？
推荐答案
有关maxValue（最大值）的小值，这是合理的生成内存中的所有整数数组，那么你可以使用Fisher-Yates洗牌但只执行前n个步骤。
For small values of maxValue such that it is reasonable to generate an array of all the integers in memory then you can use a variation of the Fisher-Yates shuffle except only performing the first n steps.
如果n小于maxValue分别小得多，你不希望生成整个数组，那么你可以使用这个算法：
If n is much smaller than maxValue and you don't wish to generate the entire array then you can use this algorithm:
- 在保持数量的排序列表L回升至今，初始为空。
- 选择一个随机数x 0为maxvalue - （L中的元素）
- 对于升每个号码，如果它大于或等于x越小，添加1到x
- 添加x的值调整到排序列表和重复。
如果n是非常接近maxValue（最大值），那么你可以随意挑选的的元素不是的结果中，然后找到该组的补充。
If n is very close to maxValue then you can randomly pick the elements that aren't in the result and then find the complement of that set.
下面是另一种算法，该算法简单，但具有潜在的无限执行时间：
Here is another algorithm that is simpler but has potentially unbounded execution time:
- 保存元素的集合S挑到目前为止，初始为空。
- 挑一些随机介于0和计算最大值。
- 如果该号码不在s时，添加到第
- 回到步骤2，直到S有n个元素。
在实践中，如果n是小为maxvalue是大的，这将是很好的足以满足大多数目的。
In practice if n is small and maxValue is large this will be good enough for most purposes.
这篇关于随机选择一组不同的整数的最有效的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
