arrays - 使用右移按位运算符生成列表中的所有唯一项

Question

我试图理解 MIT 在线类(class)中的一些代码，这些代码使用右移按位运算符生成列表的所有唯一组合

# generate all combinations of N items
def powerSet(items):
    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])
        yield combo

我理解的提升 if (i >> j) % 2 == 1: 将整数右移 N 次并查看最后一位是否为 1 然后添加它独特组合的列表。但是，我不确定这是如何在列表中生成所有唯一集的。谁能用通俗易懂的英语解释一下？

Answer 1

这个算法的关键是 N 项可能有 2**N 种不同的组合。这很容易理解:对于每个项目，我们都可以取或不取一个项目；假设 N 个项目的集合有 M 种不同的组合，那么将一个项目添加到集合中使得 2*M 种组合成为可能。

但是组合中项目的这种“是/否”状态强烈地提醒了位(或者，实际上，数字的二进制表示)。如果我们有 2 个项目，我们可以将所有组合写成如下。

00
01
10
11

现在，为了生成所有组合，我们只需颠倒这个过程:我们循环遍历从 0 到 2**N-1 的数字，然后看看它对应的是什么组合。比如说，对于数字 2(或二进制表示中的 10)，组合将仅包含一个索引为 1 的项目。即我们正在查看当前数字的二进制表示(上面代码中的 i)，并循环遍历它的数字，测试第 j 个数字是否为 1((i >> j) % 2 == 1).如果是这样，我们将一个项目添加到组合中。