我目前正在遵循MITx的6.00.2x，要求我们在底部提出一种电源设置发生器的变体。
但是在我研究变体之前，我什至不了解给定生成器发生了什么。特别：
(i >> j) % 2 == 1，而实际上整个for j in range(N):块吗？据我所知，i >> j偏移的二进制i通过j，然后返回的该十进制表示偏移二进制数。但是我绝对不知道为什么一开始在电源集生成器中甚至需要二进制文件，更不用说此条件的必要了。我知道，对于任何给定的集合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
因此，此处的算法首先观察到的任何子集{1,...,N}都可以视为一个函数f:{1,...,N}->{0,1}，即特征函数。这个怎么运作？好吧，ifA是{1,...,N}then的子集，f由f(x)=0if xnot inA和f(x)=1else给出。
现在另一个观察结果是，任何函数f:{1,...,N}->{0,1}都可以编码为二进制N位数：如果第j个位为1 f(j)=1，否则为0。
因此，如果我们要生成{1,..,N}它的所有子集，就足以生成所有length的二进制数N。那么有多少这样的数字呢？当然可以2**N。并且由于介于0和之间的每个数字2**N - 1（-1因为我们从计数0）唯一地对应于的某个子集，{1,...,N}因此我们可以简单地遍历它们。这就是for i in range(2**N):循环的来源。
但是我们不只是处理的子集{1,...,N}，我们实际上有一些未知items的length集/列表N。因此，如果A是的子集{1,...,N}，则意味着A是之间的数字0，2**N - 1那么我们如何将其转换为的子集items？好吧，再次，我们使用一个事实，即该位1对应于“处于设置中”而该位0对应于“未处于设置中”。那就是(i >> j) % 2 == 1从哪里来的。它仅表示“如果第j位为1”，其结果是导致“第j个元素应位于子集中”。
您的代码有一个小问题。您应该屈服而不是返回：
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"]))
这是子集的二进制编码的示例。说你有一个清单
[“苹果”，“香蕉”，“梨”]
它具有3个元素，因此我们正在研究（二进制）长度3的数量。因此，这里是所有可能的子集及其按“循环”顺序的编码：
000 == []
001 == [“ apple”]
010 == [“ banana”]
011 == [“ apple”，“ banana”]
100 == [“梨”]
101 == [“ apple”，“梨”]
110 == [“香蕉”，“梨”]
111 == [“苹果”，“香蕉”，“梨”]
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句