Python n 选择 k 的代码 - 它是如何工作的？

Question

我遇到了这段代码：

https://diego.assencio.com/?index=50ed9dcd9009dd70c3a2f8822271e4c7

def bitmasks(n,m):
    if m < n:
        if m > 0:
            for x in bitmasks(n-1,m-1):
                yield (1 << (n-1)) + x
            for x in bitmasks(n-1,m):
                yield x
        else:
            yield 0
    else:
        yield (1 << n) - 1
 
# print each value as a 4 bit binary number
for b in bitmasks(4,2):
    print('{:04b}'.format(b))

更清晰一点的版本：

def bitmasks(n, m):
    if n == m:
        yield (1 << n) - 1
    elif m > 0:
        for x in bitmasks(n-1, m-1):
            yield (1 << (n-1)) + x
        for x in bitmasks(n-1, m):
            yield x
    else:
        yield 0

这会使用位掩码生成 n choose k 的所有排列。有人可以向我解释它是如何工作的吗？我发现很难直观地掌握正在发生的事情。

我知道 (1 << (n - 1)) + x 是将 2^(n - 1) 添加到 x，但这如何生成所有正确的排列？

编辑：

我的理解如下：

对于n choose k，我们需要从n个位置生成一个k 1's的序列。 n 个位置中的每一个都可以是 1 or 0.

为此，这段代码使用了某种递归魔法：

代码将一直向下递归，直到遇到 m == n 或以下分支：

else:
  yield (1 << n) - 1

根据定义，这会将最右边的 k 位设置为 1。

现在，以此为起点，我们向上递归树。这是我有点迷路的地方：

首先，第一个for循环。我们将 (1 << (n - 1)) 添加到数字中， x 存储在我们的迭代器中。这会将 (n - 1)th 位设置为 1?

我不太确定这两个 for 循环是如何构造结果的。

Answer 1

这个算法递归地工作，所以为了解释它是如何工作的，我将依靠“信仰的飞跃”——我们应该假设递归调用做正确的事情，and from that我们想推断出函数整体做正确的事。

不用递归调用解决的基本情况很简单：

如果m == n只有一种组合，由n连续1位组成。这等于(1 << n) - 1；如果你不确定为什么，这对你来说是一个很好的练习，你可以自己弄清楚。
如果m == 0同样只有一种组合，其中没有1位。这等于 0.

对于递归情况，我们有 n 个位置，我们希望将 m 1 位放入其中。所有组合的集合可以分为两个子集：

第n位为1的组合。我们可以通过递归地找到剩余m - 1个1位的组合来生成所有这样的组合n - 1个位置，在第n个位置加1位。我们使用表达式 1 << (n - 1) 将 1 位放入第 n 个位置，其中移位 n - 1 而不是 n 因为我们从 0.
第n位为0的组合。这意味着剩余的n - 1个位置必须具有所有m个1位，这是通过递归调用找到的.

Python n 选择 k 的代码 - 它是如何工作的？

Python Code for n Choose k - How does it work?

python

math

permutation