从n中选择k

Question

我想k在n没有选择相同数字两次的情况下随机选择均匀的元素.这有两个简单的方法.

1. 列出所有n可能性.将它们洗牌(你不需要通过执行Fisher Yates的第一步来改变它们的 所有n数字).选择第一个.这种方法需要时间(假设分配一个大小的数组需要 时间)和空间.如果相对于非常小,这是一个问题.kkkO(k)nO(1)O(n)kn
2. 存储一组看到的元素.从中随机选择一个数字[0, n-1].当元素在集合中时,然后选择一个新数字.这种方法占用O(k)空间.运行时分析要复杂一些.如果k = theta(n)那时运行时间是 O(k*lg(k))=O(n*lg(n))因为它是优惠券收集器的问题.如果k相对较小n则需要稍微多于O(k)因为选择相同数字两次的概率(尽管很低).这在空间方面优于上述解决方案,但在运行时方面更差.

我的问题:

是否有O(k)时间,O(k)空间算法为所有k和n？

Answer 1

使用O(1)哈希表,可以使部分Fisher-Yates方法在O(k)时间和空间中运行.诀窍只是在哈希表中只存储数组中已更改的元素.

这是Java中的一个简单示例:

public static int[] getRandomSelection (int k, int n, Random rng) {
    if (k > n) throw new IllegalArgumentException(
        "Cannot choose " + k + " elements out of " + n + "."
    );

    HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(2*k);
    int[] output = new int[k];

    for (int i = 0; i < k; i++) {
        int j = i + rng.nextInt(n - i);
        output[i] = (hash.containsKey(j) ? hash.remove(j) : j);
        if (j > i) hash.put(j, (hash.containsKey(i) ? hash.remove(i) : i));
    }
    return output;
}

这段代码分配了一个2× k桶的HashMap 来存储修改后的元素(这应该足以确保哈希表永远不会重新散列),并且只运行部分Fisher-Yates shuffle.

这是对Ideone的快速测试 ; 它从三个30,000次中挑选出两个元素,并计算每对元素的选择次数.对于无偏差的随机播放,每个有序对应出现大约5,000(±100左右)次,除了两个元素相等的不可能的情况.