如何计算powerset中的set数？

Question

给定一个整数列表，是否有一个算法来计算powerset中的集合数？这不应该包括空集，并且，例如，{1,2,3}与{}相同，因此它们不应该被计数两次（即powerset）。在

注意：列表中的元素不一定是唯一的。

Answer 1

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 2

集合被定义为只包含唯一/不同的元素。集合的powerset中的集合数是2^elements_in_set。powerset包含空集，因此您需要的是2^elements_in_set - 1。在

因此，一个列表集合的powerset中的集合数是2^unique_elements_in_list，没有空集的数量是2^unique_elements_in_list - 1。在

---

另一种考虑方法是创建一个位数组，其大小与唯一元素的数量相同。数组中的每个位对应于该元素是否在特定的powerset元素中。假设你的元素是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    

所以你最终只能用二进制数。你能用n二进制数字组成多少个数字？2^n。除零外有多少？2^n - 1。在

---

为了实际生成powerset，这里有一些代码。注意，它使用列表是为了方便。在

^{pr2}$

示例：

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

您可以使用itertoolscombinations函数来生成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

结果：

^{pr2}$