这套所有设置一行功能是干什么的？

Question

我在python wiki上发现了这一行函数，它创建了一组可以从作为参数传递的列表中创建的所有集合。

f = lambda x: [[y for j, y in enumerate(set(x)) if (i >> j) & 1] for i in range(2**len(set(x)))] 

有人能解释一下这个函数是如何工作的吗？

Answer 1

要构建powerset，迭代2**len(set(x))会为您提供该集合的所有二进制组合。

range(2**len(set(x))) == [00000, 00001, 00010, ..., 11110, 11111] 

现在你只需要如果该位被i设置，看是否需要把它列入设定，如：测试：

>>> i = 0b10010 
>>> [y for j, y in enumerate(range(5)) if (i >> j) & 1] 
[1, 4] 

虽然我不知道如何高效的IT每次迭代都会给set(x)打电话。有一个小黑客会避免：

f = lambda x: [[y for j, y in enumerate(s) if (i >> j) & 1] for s in [set(x)] for i in range(2**len(s))] 

一对夫妇的其他形式使用itertools：

import itertools as it 
f1 = lambda x: [list(it.compress(s, i)) for s in [set(x)] for i in it.product((0,1), repeat=len(s))] 
f2 = lambda x: list(it.chain.from_iterable(it.combinations(set(x), r) for r in range(len(set(x))+1))) 

注：这最后一个可以只返回一个迭代VS列表，如果你删除list()视这个用例可以节省一些内存。

看着25张的随机数0-50名单的一些计时：

%%timeit binary: 1 loop, best of 3: 20.1 s per loop 
%%timeit binary+hack: 1 loop, best of 3: 17.9 s per loop 
%%timeit compress/product: 1 loop, best of 3: 5.27 s per loop 
%%timeit chain/combinations: 1 loop, best of 3: 659 ms per loop 

Answer 2

让我们把它改写了一下，打破它一步一步：

f = lambda x: [[y for j, y in enumerate(set(x)) if (i >> j) & 1] for i in range(2**len(set(x)))] 

相当于：

def f(x): 
    n = len(set(x)) 
    sets = [] 
    for i in range(n): # all combinations of members of the set in binary 
     set_i = [] 
     for j, y in enumerate(set(x)): 
      if (i>>j) & 1: #check if bit nr j is set 
       set_x.append(y) 
     sets.append(set_i) 
    return sets 

像[1,2,3,4]的输入列表中，将出现以下情况：

n=4 
range(2**n)=[0,1,2,3...15] 

其中，以二进制为：

0,1,10,11,100...1110,1111 

枚举使Y的元组的指数，所以在我们的例子：

[(0,1),(1,2),(2,3),(3,4)] 

的(i>>j) & 1部分可能需要一些解释。 (i>>j)将数字ij移位到右边，例如，十进制：4>>2=1，或二进制：100>>2=001。 &是位运算符and。这将检查两个操作数的每个位是否为1，并将结果作为数字返回，如同过滤器：10111 & 11001 = 10101。

在我们的示例中，它检查位置j的位是否为1.如果是，则将相应的值添加到结果列表中。通过这种方式，组合的二进制映射被转换为返回的列表列表。