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

Question

此代码是 return 集合大小 n (EPI 5.15) 中大小为 k 的子集。也就是说，取 n > 0，k <= 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)]

我的解决方案（大错特错）

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 的 <0, 1, 2, ..., n-1> 部分中选取一个元素，不重复。首先从数组A中取出r，与A[0]交换；然后选择另一个 r 并将其与 A[1] 交换...直到我们填充 A[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]

为了通过模仿数组 <0, 1, 2, ..., n-1> 将 space 复杂度从 O(n) 降低到 O(k)，我们将上面的代码更改为一个使用散列 table 的官方解决方案，我们从中 select 一个要包含在子集中的元素。问题出在我使用哈希 table 的方式与原始答案不同，但我不知道为什么。

Answer 1

，最后一个好像没有基本意义。像

这样的作业

            H[i] = H[r], i

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

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

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

第二行的get()是more-than-less没用的，因为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

现在将实现概念上的“交换”逻辑 if 在循环的顶部总是如此。 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] 中，现在也在 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

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

Computing a random subset in Python - what's wrong in my code?

python

random

hash

hashtable

官方解决方案

改成官方解决方案（错误）

我的解决方案（大错特错）

底层逻辑

编辑：最新代码的新版本