-1

给定一个整数列表，是否有一种算法可以计算幂集中的集合数？这不应包括空集，例如，{1,2,3}与 相同{2,3,1}，因此不应将它们计算两次（即幂集）。

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

4

4 回答 4

2

集合被定义为仅包含唯一/不同的元素。一个集合的幂集中的集合数是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

所以你真的只是最终以二进制计算。你可以用n二进制数组成多少个数字？2^n. 除了零还有多少？2^n - 1.

要实际生成 powerset，这里有一些代码。请注意，为方便起见，它使用列表。

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 提高到一个幂比生成整个集合来计算它要容易得多！

于 2013-10-31T15:54:13.427 回答
0

您可以使用 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')
于 2013-10-31T15:48:58.130 回答
0 
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
于 2013-10-31T15:52:40.797 回答
0

重复项对 powerset 中的集合数量没有影响 - 您可以简单地使用 powerset 公式 - （如下所示），其中是唯一元素的数量。2n-1n

动机 - 每个独特的元素可以被选择，也可以不被选择（我们选择哪个事件并不重要），所以每个独特元素有 2 种可能性，因此总共有可能性。是为了排除空集。2*2*...*2 = 2n-1

带有重复项的“集”：

如果我们假设每个“集合”可以包含重复项（但出现次数不超过输入中的次数），则更有趣的问题是生成幂集。

因此，对于类似的东西1,2,2,3，一些需要计算的“集合”将是2,2,3, 1,2,2,2,2等。

让我们考虑一下。

对于1,2,2,3，我们可以选择 1 或不选择它（2 种可能性），我们可以选择 0-2 个二的（3 种可能性），我们可以选择 3 或不选择它（2 种可能性）。

请注意，每个不同的元素都有number of occurrences + 1可能。

所以，伪代码：

setCount = 1
for each distinct element e
   setCount *= 1 + number of occurrences of e
output setCount-1
于 2013-10-31T16:57:53.483 回答