在 Python 中计算随机子集 - 我的代码出了什么问题？

Question

该代码是返回具有尺寸k的子集，从设置尺寸n（EPI 5.15）返回。也就是说，n＆gt; 0，k＆lt; = n，从n（假设上）形成一个集合{0，1，2，...，n-1}，我们从中选择k元素以形成子集。 NCK有选择子集的可能性，我们希望将其均匀挑选，我们也希望该子集中的置换也是随机的。代码有三个版本 - 来自官方解决方案，我的调整和我自己的解决方案。后两个是错误的，但我不知道为什么。我将在三个代码下方解释算法的要旨。

官方解决方案

def random_subset(n: int, k: int) -> List[int]:
    H = {}
    for i in range(k):
        r = random.randrange(i, n)
        rmap = H.get(r, r)
        imap = H.get(i, i)
        H[r] = imap
        H[i] = rmap
    return [H[i] for i in range(k)]

更改为官方解决方案（错误）

def random_subset(n: int, k: int) -> List[int]:
    H = {}
    for i in range(k):
        r = random.randrange(i, n)
        H[r] = H.get(i, i)
        H[i] = H.get(r, r)
    return [H[i] for i in range(k)]

（DEAD错误）

def random_subset(n: int, k: int) -> List[int]:
    H = {}
    for i in range(k):
        r = random.randrange(i, n)
        if r in H:
            H[i], H[r] = H[r], i
        else:
            H[i], H[r] = r, i
    return [H[i] for i in range(k)]

我的解决方案（错误）逻辑的解决方案

我们从数组a，＆lt; 0，1，2，...，n-1＆gt; Gt;中选择一个元素，而无需重复。首先，从数组A中挑选R，然后用[0]将其交换；然后选择另一个R并用[1]交换它...直到我们填充[K-1]，总共有K元素，例如以下代码：

'''
A = <0, 1, 2, ..., n-1>
i    0  1  2       n-1
'''

def random_sampling(k, A):
    for i in range(k):
        r = random.randrange(i, len(A))
        A[i], A[r] = A[r], A[i]

A = [i for i in range(n)]
k = some_constant
random_sampling(k, A)
answer = A[:k]

将空间复杂性从O（N）降低到O（ k）通过模仿数组＆lt; 0，1，2，...，n-1＆gt;，我们将右上的代码更改为官方解决方案，该解决方案使用哈希表，我们从中选择了一个要包含在子集中的元素。我的使用方式与原始答案不同，但我不知道为什么会出现问题。

Answer 1

，最后一项似乎没有基本意义。像这样的赋值

            H[i] = H[r], i

将 H[i] 绑定到 2 元组，而不是整数。

中间（第二个）是踩自己的脚趾：

        H[r] = H.get(i, i)
        H[i] = H.get(r, r)

第二行中的 get() 毫无用处，因为 H[r] 已被绑定在上面的行中。当第二行执行时，r总是在H中，因此这两行是相同的，例如，

        temp = H.get(i, i)
        H[i] = H[r] = temp

这很明显不是你打算这样做。

顺便说一句，如果您出于某种原因热衷于减少行数，这应该可行：

    H = {}
    for i in range(k):
        r = random.randrange(i, n)
        H[i], H[r] = H.get(r, r), H.get(i, i)
    return [H[i] for i in range(k)]

但我发现第一个版本是最清晰的。

编辑：最后一个代码的新版本

最后一个版本已更改为：

    for i in range(k):
        r = random.randrange(i, n)
        if r in H:
            H[i], H[r] = H[r], i
        else:
            H[i], H[r] = r, i

现在将实现概念上的“交换”逻辑如果情况总是如此，在顶部循环。 H.get(i, i) == i。但事实并非如此，因此它可能会失败。

例如，从 n=9 和 k=5 开始（这并不微妙 - 几乎是任意的）。在第一次循环迭代 (i=0) 中，假设选择了 r=1。然后将 H[0] 设置为 1，将 H[1] 设置为 0。这样就可以了。 但是，现在 H.get(1, 1) 不是 1，而是 0。这可能会给下一步带来麻烦。

在下一次迭代 (i=1) 中，假设选择了 r=5。所以代码

            H[i], H[r] = r, i # which is
            H[1], H[5] = 5, 1

确实糟糕！现在 0（在 H[1] 中）不再在 H 中，并且 1 在 H 中出现两次（它在 H[0] 中） code>，现在它也在 H[5] 中）。这根本不是“交换”。

顺便说一句，还有另一种我更喜欢的写法，因为它非常明确地表明，一旦选择了子集元素，该决定将永远不会改变。它还减少了 H 的大小：

def random_subset(n, k):
    H = {}
    result = []
    for i in range(k):
        r = random.randrange(i, n)
        result.append(H.get(r, r))
        H[r] = H.pop(i, i)
    return result