随机选择一组不同整数的最有效方法

Question

我正在寻找最有效的算法来随机选择一组n个不同的整数,其中所有整数都在某个范围[0..maxValue].

约束:

• maxValue大于n,可能更大
• 我不在乎输出列表是否排序
• 必须以相同的概率选择所有整数

我最初的想法是构造一个整数列表[0..maxValue]然后随机提取n个元素而不替换.但这似乎效率很低,特别是如果maxValue很大的话.

更好的解决方案？

Answer 1

这是一个最优算法,假设我们被允许使用散列图.它在O(n)时间和空间(而不是O(maxValue)时间运行,这太贵了).

它基于Floyd的随机样本算法.有关详细信息,请参阅我的博客文章.代码是Java:

private static Random rnd = new Random();

public static Set<Integer> randomSample(int max, int n) {
    HashSet<Integer> res = new HashSet<Integer>(n);
    int count = max + 1;
    for (int i = count - n; i < count; i++) {
        Integer item = rnd.nextInt(i + 1);
        if (res.contains(item))
            res.add(i);
        else
            res.add(item);
    }
    return res;
}

Answer 2

对于较小的maxValue值,以便在内存中生成所有整数的数组是合理的,那么除了仅执行第一步之外,您可以使用Fisher-Yates shuffle的变体n.

如果n小于maxValue并且您不希望生成整个数组,那么您可以使用此算法:

1. 保留l到目前为止选择的数字的排序列表,最初为空.
2. 选择x0和maxValue- 之间的随机数(元素l)
3. 对于l小于或等于的每个数字x,将1加1x
4. 将调整后的值添加x到排序列表中并重复.

如果n非常接近maxValue那么你可以随机选择不在结果中的元素,然后找到该集合的补充.

这是另一种更简单但可能无限制执行时间的算法:

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

在实践中,如果n小而且maxValue很大,这对于大多数目的来说足够好.