フルセットをメモリに展開せずに、パワーセットの要素にインデックスを付けられるようにしたい (a la itertools)
さらに、インデックスをカーディナリティ順に並べたいと思います。したがって、インデックス 0 は空のセットである必要があり、インデックス 2**n - 1 はすべての要素である必要があります
私がこれまでに見つけたほとんどの文献は、電力セットを誘導的に生成することに関するものです。任意のインデックスに飛び込むことはできません。このインデックス作成の動機は、分散実行のために問題をスライスすることです。リモート マシンがクラスター間で反復子参照を共有することなく、どこにでも飛び込める場合に役立ちます。
編集：Blckknghtは、私が追求した解決策を提案しました。これは以下に示されています
from scipy.misc import comb
def kcombination_to_index(combination):
index = 0
combination = sorted(combination)
for k, ck in enumerate(combination):
index += comb(ck, k+1, exact=True)
return index
def index_to_kcombination(index, k):
result = []
for k in reversed(range(1, k+1)):
n = 0
while comb(n, k, exact=True) <= index:
n +=1
result.append(n-1)
index -= comb(n-1, k, exact=True)
return result
class PowerSet:
def __init__(self, elements):
self.elements = elements
def __len__(self):
return 2 ** len(self.elements)
def __iter__(self):
for i in range(len(self)):
yield self[i]
def __getitem__(self, k):
if not isinstance(k, int):
raise TypeError
#k=0 is empty set,
#k= 1 - 1+n returns subsets of size 1
for subset_size in range(len(self.elements) + 1):
number_subsets = comb(len(self.elements), subset_size, exact=True)
if k >= number_subsets:
k -= number_subsets
else:
break
#we now want the kth element of a possible permutation of subset_size elements
indeces = index_to_kcombination(k, subset_size)
return map(lambda i: self.elements[i], indeces)
if __name__ == "__main__":
print "index of combination [8, 6, 3, 1, 0] is", kcombination_to_index([8, 6, 3, 1, 0])
print "5 combination at position 72 is", index_to_kcombination(72,5)
ps = PowerSet(["a", "b", "c", "d"])
for subset_idx in range(len(ps)):
print ps[subset_idx]