随机选择一组不同整数的最有效方法 [英] 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 shuffle 除了只执行前 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:

1. 保持一个排序列表 l 到目前为止选择的数字，最初是空的.
2. 在 0 和 maxValue 之间选择一个随机数 x - (l 中的元素)
3. 对于l中的每个数字，如果小于或等于x，给x
加1
4. 将x的调整值加入到排序列表中并重复.

1. Keep a sorted list l of number picked so far, initially empty.
2. Pick a random number x between 0 and maxValue - (elements in l)
3. For each number in l if it smaller than or equal to x, add 1 to x
4. Add the adjusted value of x into the sorted list and repeat.

如果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:

1. 保留一组 s 到目前为止选择的元素，最初为空.
2. 在 0 到 maxValue 之间随机选择一个数字.
3. 如果数字不在 s 中，请将其添加到 s.
4. 回到第 2 步，直到 s 有 n 个元素.

1. Keep a set s of element picked so far, initially empty.
2. Pick a number at random between 0 and maxValue.
3. If the number is not in s, add it to s.
4. Go back to step 2 until s has n elements.

在实践中，如果 n 小而 maxValue 大，这对于大多数用途来说已经足够了.

In practice if n is small and maxValue is large this will be good enough for most purposes.

这篇关于随机选择一组不同整数的最有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！