1行の関数が行うすべてのセットのセットは何ですか？

Question

私はpython wikiでこの1行の関数を見つけました。これは、引数として渡されるリストから作成できるすべてのセットのセットを作成します。

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] 

私はどのように効率的なことはわからないけどすべての反復に対してset(x)への呼び出しが与えられます。他の形態のカップルがitertoolsを使用して

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))] 

：

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))) 

注：それを回避する小さなハックがありますが、依存list()を削除する場合は、この最後のものは、単にリスト対のiterableを返すことができますユースケースを使用すると、メモリを節約できます。

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

と同等です：それを少し書き換え、ステップバイステップでそれを打破してみましょう

%%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

：

25の乱数0-50のリストのいくつかのタイミングでみると： [1,2,3,4]ような入力リストの

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 

、次の処理が行われます

0バイナリである、

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

：(i>>j) & 1部分はいくつかの説明が必要になる場合があります

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

：

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

私たちのケースでので列挙には、そのインデックスで、yのタプルになります。 (i>>j)は、右に数字ijをシフトします。小数は：4>>2=1、またはバイナリ：100>>2=001です。 &はビット単位でand演算子です。これは、両方のオペランドの各ビットが1であるかどうかをチェックし、結果を数値として返します。フィルタのように動作します：10111 & 11001 = 10101。

この例では、jのビットが1であるかどうかをチェックします。値が1の場合、対応する値が結果リストに追加されます。この方法で、組み合わせのバイナリマップがリストのリストに変換され、返されます。