从n个元素中选择k个的问题

Question

从n个元素中选择k个的问题

algorithmshuffle

23

我希望从可能的n个元素中均匀随机选择k个元素，而不重复选择相同的数字。有两种简单的方法来解决这个问题。

列出所有 n 种可能性。将它们洗牌（你不需要洗牌所有的 n 个数字，只需执行 Fisher Yates 的前 k 步）。选择前 k 个。这种方法需要 O(k) 时间（假设分配大小为 n 的数组需要 O(1) 时间），并且需要 O(n) 空间。如果 k 相对于 n 很小，则会出现问题。
存储一组已见元素。从 [0, n-1] 中随机选择一个数字。当元素在集合中时，选择一个新数字。这种方法需要 O(k) 空间。运行时间稍微复杂一些。如果 k = theta(n)，则运行时间为 O(k*lg(k))=O(n*lg(n))，因为这是收集优惠券问题。如果 k 相对于 n 很小，则需要略多于 O(k) 的时间，因为有可能（虽然很低）两次选择相同的数字。与上述解决方案相比，这种方法在空间方面更好，但在运行时间方面更差。

我的问题：

是否存在一个对于所有的 k 和 n 都具有 O(k) 时间复杂度和 O(k) 空间复杂度的算法？

- Benjy Kessler

我不认为你可以避免包括输入数组所占用的空间，从而达到O(n)的空间复杂度。你有n个元素，存储它所需的空间将随着n的增长而增加。 - Asad Saeeduddin

你不需要存储输入数组，只需存储数字n和选择的第k个元素。 - Benjy Kessler

那么，给定数字n和k，你的子程序如何从一个没有给定的n个元素的集合中均匀随机选择k个元素？ - Asad Saeeduddin

很简单，函数rand()选择一个在[0，RAND_MAX]范围内的数字，而不需要存储大小为RAND_MAX的数组。 - Benjy Kessler

1

我不需要适用于任何集合的算法。只需要针对数字集合[0，n]。 - Benjy Kessler

显示剩余4条评论

3个回答

2

你的第二种方法在平均情况下并不需要花费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)的平均时间和空间复杂度算法。

- Douglas Zare

非常有趣的观察。问题提到了_O(k log k)_，而不是_Θ(k log k)_，并且没有假设_k_或_k>n/2_的补集优化。此外，值得一提的是，您假定了_O(1)_的集合成员资格测试（这也可能是OP的假设，但很难确定）。 - kyrill

0

你可以使用以下算法（使用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个条目引用即可。

- Gerard

1

这正是我给出的第一个选项。我想要一个时间复杂度为O(k)的算法。 - Benjy Kessler

这个算法的时间复杂度为O(k)，它受到Θ(k)的限制。 - Gerard

1

我指的是O(k)时间和空间。 - Benjy Kessler

你需要将输入存储在某个地方。你是否正在寻找一种使用“半代数集”来解决问题的解决方案？如果是这样，你可以减少存储要求。 - Gerard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ilmari Karonen · Accepted Answer

使用具有O(1)哈希表，可以使部分费舍尔耶茨方法在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;
}

这段代码分配了一个HashMap，其中包含2×k个桶以存储修改后的元素（应该足够确保哈希表永远不会重新散列），并对其进行部分 Fisher-Yates 洗牌。这里是在 Ideone 上的快速测试；它从三个元素中选择两个元素30,000次，并计算每个元素对被选中的次数。对于无偏洗牌，每个有序对应该出现大约5,000次（误差范围为100左右），除了两个元素都相等的不可能情况。