python - 为什么这个幂集生成器需要按位运算符？

Question

我目前正在关注 MITx 的 6.00.2x，我们被要求提出底部那个的 powerset generator 的变体。

但在我可以处理变体之前，我什至不了解给定的生成器发生了什么。具体来说:

1. (i >> j) % 2 == 1 以及整个 for j in range(N): block 是做什么的？我明白 i >> j 转变j对i的二进制，然后返回的十进制表示那个移位的二进制数。但我完全不知道为什么二进制甚至首先需要在 powerset 发电机中，更不用说这个条件的必要性。

2. 我知道对于任何给定的集合 A，基数 n，其幂集的基数是 2**n - 因为对于 A 的每个子集每个成员要么在要么不在，我们重复 n 次。

   for i in range(2**N): 是这样做的吗？即遍历 2**n 个子集并包含或不包含该集合的任何给定成员？

我尝试使用 items=['apple,'banana','orange'] 和 items=[1,2,3] 运行它，但都返回了一个空列表，这使得它更加困惑。

def powerSet(items):
    # generate all combinations of N items, items is a Python list
    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(2**N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        return combo

Answer 1

所以这里的算法从观察 {1,...,N} 的任何子集开始可以看作一个函数 f:{1,...,N}->{0,1} ，即特征函数。怎么运行的？好吧，如果 A是 {1,...,N} 的子集然后f由 f(x)=0 给出如果x不在 A和 f(x)=1否则。

现在另一个观察结果是任何函数 f:{1,...,N}->{0,1}可以编码为N的二进制数位:如果 f(j)=1，则第 j 位为 1否则为 0。

因此，如果我们想要生成 {1,..,N} 的所有子集生成长度为 N 的所有二进制数就足够了.那么这样的数字有多少呢？当然2**N .并且由于 0 之间的每个数字和 2**N - 1 ( -1 因为我们从 0 开始计算)唯一对应于 {1,...,N} 的某个子集然后我们可以简单地遍历它们。那就是 for i in range(2**N): 的地方循环来自。

但我们不只是处理 {1,...,N} 的子集，我们实际上有一些未知的集合/列表 items长度N .所以如果A是 {1,...,N} 的子集, 意思是 A是 0 之间的数字和 2**N - 1那么我们如何将它转换为 items 的子集呢？ ？好吧，我们再次使用 1 位这一事实对应于“在集合中”和位0对应于“不在集合中”。这就是 (i >> j) % 2 == 1 的地方来自。它只是表示“如果第 j 位为 1”，结果导致“第 j 个元素应该在子集中”。

您的代码存在一个小问题。你也许应该 yield 而不是 return:

def powerSet(items):
    N = len(items)
    for i in range(2**N):
        combo = []  # <-- this is our subset
        for j in range(N):
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo  # <-- here we yield it to caller

subsets = list(powerSet(["apple", "banana", "pear"]))

---

这是子集二进制编码的示例。假设你有一个列表

["apple", "banana", "pear"]

它有 3 个元素，所以我们正在查看(二进制)长度为 3 的数字。所以这里是所有可能的子集及其在“循环”顺序中的编码:

000 == []

001 == ["apple"]

010 == ["banana"]

011 == ["apple", "banana"]

100 == ["pear"]

101 == ["apple", "pear"]

110 == ["banana", "pear"]

111 == ["apple", "banana", "pear"]