python - パワーセットのセット数を数える方法は?

Question

整数のリストが与えられた場合、パワーセット内のセット数をカウントするアルゴリズムはありますか? これには空のセットを含めるべきではなく、たとえば、{1,2,3}と同じ{2,3,1}であるため、2 回カウントすることはできません (つまり、powerset)。

注: リストの要素は必ずしも一意ではありません。

Answer 1

セットは、一意の要素のみを含むものとして定義されます。セットのパワーセットのセット数は です2^elements_in_set。powerset には空のセットが含まれているため、必要なのは です2^elements_in_set - 1。

したがって、リストのセットのべき集合のセットの数は2^unique_elements_in_listであり、空セットを除いた数は です2^unique_elements_in_list - 1。

---

別の考え方としては、一意の要素の数と同じサイズのビット配列を作成することです。配列内の各ビットは、その要素がその特定のパワーセット要素にあるかどうかに対応します。要素が 9、7、4 であるとします。マッピングは次のようになります。

powerset element | 9 | 7 | 4  
-----------------+---+---+---
[]               | 0 | 0 | 0 
[4]              | 0 | 0 | 1
[7]              | 0 | 1 | 0
[4, 7]           | 0 | 1 | 1 
[9]              | 1 | 0 | 0
[4, 9]           | 1 | 0 | 1
[7, 9]           | 1 | 1 | 0  
[4, 7, 9]        | 1 | 1 | 1    

したがって、実際にはバイナリでカウントすることになります。n2進数でいくつの数を作ることができますか? 2^n. ゼロを除いていくつ？2^n - 1.

---

パワーセットを実際に生成するためのコードを次に示します。便宜上、リストを使用していることに注意してください。

def gen_powerset(l):
    if not l:
        yield []
        return
    for sub_powerset in gen_powerset(l[1:]):
        yield sub_powerset
        yield [l[0]] + sub_powerset

例：

>>> list(gen_powerset(list(set([1, 4, 2, 2, 3]))))
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], 
 [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
>>> len(list(gen_powerset(list(set([1, 4, 2, 2, 3])))))
16

16 は2^4であることに注意してください。これは、 の一意の要素の数です[1, 4, 2, 2, 3]。

ただし、カウントするためだけにセット全体を生成するよりも、2 を累乗する方がはるかに簡単です!

Answer 2

from itertools import chain, combinations

i = set([1, 2, 3])

for z in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)):
    print z 

Answer 3

itertoolsの組み合わせ関数を使用して、繰り返しなしで S のすべてのサブセットを生成できます。

def powerset(iterable):
    result = set()
    for l in xrange(1, len(iterable) + 1):
        for subset in itertools.combinations(iterable, l):
            result.add(subset)
    return sorted(result, key=len)

S = ['x', 'y' ,'z', 'y']
for subset in powerset(S):
    print subset

結果：

('z',)
('y',)
('x',)
('z', 'y')
('x', 'y')
('y', 'y')
('x', 'z')
('y', 'z')
('y', 'z', 'y')
('x', 'y', 'z')
('x', 'z', 'y')
('x', 'y', 'y')
('x', 'y', 'z', 'y')