6

我正在尝试使用生成器在 Python 中构建给定集合的子集列表。说我有

set([1, 2, 3])

作为输入，我应该有

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

作为输出。我怎样才能做到这一点？

4

3 回答 3

18

最快的方法是使用 itertools，尤其是链和组合：

>>> 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 
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)
>>>

如果您需要生成器，只需使用 yield 并将元组转换为集合：

def powerset_generator(i):
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)):
        yield set(subset)

然后简单地说：

>>> for i in powerset_generator(i):
    print i


set([])
set([1])
set([2])
set([3])
set([1, 2])
set([1, 3])
set([2, 3])
set([1, 2, 3])
>>>
于 2013-09-16T11:19:13.393 回答
8

从 itertools 文档的食谱部分：

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
于 2013-09-16T11:18:47.157 回答
1

我知道这太老了，但我一直在寻找同样问题的答案，经过几个小时的不成功的网络搜索，我想出了自己的解决方案。这是代码：

def combinations(iterable, r):
    # combinations('ABCDE', 3) --> ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
    pool = tuple(iterable)  # allows a string to be transformed to a tuple
    n = len(pool)  
    if r > n:  # If we don't have enough items to combine, return None
        return
    indices = range(r)  # Make a set of the indices with length (r)
    yield [pool[i] for i in indices]   Yield first list of indices [0 to (r-1)]
    while True:
        for i in reversed(range(r)):  # Check from right to left if the index is at its
                                      # max value. If everyone is maxed out, then finish
            if indices[i] != i + n - r:  # indices[2] != 2 + 5 - 3
                break                    # 2 != 4  (Y) then break and avoid the return
        else:
            return
        indices[i] += 1  # indices[2] = 2 + 1 = 3
        for j in range(i + 1, r):  # for j in []  # Do nothing in this case
            indices[j] = indices[j - 1] + 1  # If necessary, reset indices to the right of
                                             # indices[i] to the minimum value possible.
                                             # This depends on the current indices[i]
        yield [pool[i] for i in indices]  # [0, 1, 3]


def all_subsets(test):
    out = []
    for i in xrange(len(test)):
        out += [[test[i]]]
    for i in xrange(2, len(test) + 1):
        out += [x for x in combinations(test, i)]
    return out

我从 itertools doc itertools.combinations中获取了组合示例代码，并将其修改为生成列表而不是元组。当我试图弄清楚它是如何工作的（以便以后修改它）时，我做了注释，所以我会把它们放在那里，以防万一有人发现它们有帮助。最后，我创建了 all_substes 函数来查找从长度 1 到 r 的每个子集（不包括空列表，所以如果你需要它，只需从out = [[]]

于 2017-05-08T15:12:26.853 回答