从 n 中选择 k

Question

我想从可能的 n 中随机均匀地选择 k 个元素，而不是选择相同的数字两次。有两种简单的方法。

列出所有 n 种可能性。洗牌（你不需要通过执行第一个来洗牌所有 n 个数字，只有 k 个数字 k Fisher Yates 的步骤）。选择第一个k。这种方法需要 O(k) 时间（假设分配一个大小为 n 的数组需要 O(1) 次）和 O(n) space。这是一个问题，如果 k 非常相对于 n.
存储一组看到的元素。从 [0, n-1] 中随机选择一个数字。当元素在集合中时，然后选择一个新数字。这种方法需要 O(k) space。 run-time 多一点分析起来很复杂。如果 k = theta(n) 那么 run-time 是 O(k*lg(k))=O(n*lg(n)) 因为它是优惠券收藏家的问题。如果 k 相对于 n 较小，则需要稍微超过 O(k) 因为选择的可能性（尽管很低）相同的数字两次。这比上面的解决方案更好 space 但更糟 run-time.

我的问题：

是否有一个O(k)时间，O(k)space所有k和n的算法？

Answer 1

使用 O(1) hash table，部分 Fisher-Yates 方法可以在 O(k) 时间和 space 内完成运行 .诀窍就是仅将数组的 changed 元素存储在散列 table.

中

这是 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 来存储修改后的元素（这应该足以确保散列 table 永远不会被重新散列），只是运行部分 Fisher-Yates 洗牌。

Here's a quick test on Ideone；它从三个元素中挑选两个元素 30,000 次，并计算每对元素被选中的次数。对于无偏洗牌，每个有序对应该出现大约 5,000（±100 左右）次，除非两个元素相等的不可能情况。

Answer 2

您可以使用以下算法（使用 javascript 而不是伪代码）：

var k = 3;
var n = [1,2,3,4,5,6];

// O(k) iterations
for(var i = 0, tmp; i < k; ++i) {

    // Random index O(1)
    var index = Math.floor(Math.random() * (n.length - i));

    // Output O(1)
    console.log(n[index]);

    // Swap and lookup O(1)
    tmp = n[index];
    n[index] = n[n.length - i - 1];
    n[n.length - i - 1] = tmp;
}

简而言之，您将所选值与最后一项交换，并在下一次迭代样本中从减少的子集中交换。这假设您的原始集是完全独一无二的。

存储复杂度为O(n)，如果要将数字作为一个集合检索，只需参考n中的最后k个条目即可。

Answer 3

你的第二种方法平均不需要 Theta(k log k) 时间，大约需要 n/(n-k+1) + n/(n-k+2) + ... + n/n 操作，它小于 k(n/(n-k))，因为你有 k 个项，每个项都小于 n/(n-k)。对于 k <= n/2，它平均需要不到 2*k 次操作。对于k>n/2，可以随机选择一个大小为n-k的子集，取补。所以，这已经是一个 O(k) 平均时间和 space 算法。

从 n 中选择 k

Choosing k out of n

algorithm

shuffle