如何获取一组的所有子集？(幂)

Question

给定一套

{0, 1, 2, 3}

生成子集的好方法是什么:

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]

Answer 1

Python itertools页面有一个完整的powerset配方:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

输出:

>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

如果您不喜欢开头的空元组,则可以将range语句更改range(1, len(s)+1)为避免0长度组合.

Answer 2

这里有更多关于powerset的代码.这是从头开始写的:

>>> def powerset(s):
...     x = len(s)
...     for i in range(1 << x):
...         print [s[j] for j in range(x) if (i & (1 << j))]
...
>>> powerset([4,5,6])
[]
[4]
[5]
[4, 5]
[6]
[4, 6]
[5, 6]
[4, 5, 6]

Mark Rushakoff的评论适用于此:"如果您不喜欢开头的那个空元组,那么."您可以将范围语句更改为范围(1,len(s)+1)以避免0长度组合",除非在我的情况下,你for i in range(1 << x)改为for i in range(1, 1 << x).

回到这几年后,我现在写这样:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

然后测试代码看起来像这样,说:

print(list(powerset([4, 5, 6])))

使用yield意味着您不需要在单个内存中计算所有结果.预先假定主循环外的掩模是值得优化的.

Answer 3

使用powerset()包中的函数more-itertools。

产生可迭代的所有可能的子集

>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

如果您想要集合，请使用：

list(map(set, powerset(iterable)))

Answer 4

如果你正在寻找一个快速的答案,我只是在谷歌搜索"python power set"并想出了这个:Python Power Set Generator

这是来自该页面代码的复制粘贴:

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

这可以这样使用:

 l = [1, 2, 3, 4]
 r = [x for x in powerset(l)]

现在r是您想要的所有元素的列表,可以进行排序和打印:

r.sort()
print r
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]

Answer 5

def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])

Answer 6

这可以很自然地通过以下方式完成itertools.product：

import itertools

def powerset(l):
    for sl in itertools.product(*[[[], [i]] for i in l]):
        yield {j for i in sl for j in i}

Answer 7

有一个改进的powerset:

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 0:
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

Answer 8

def get_power_set(s):
  power_set=[[]]
  for elem in s:
    # iterate over the sub sets so far
    for sub_set in power_set:
      # add a new subset consisting of the subset at hand added elem
      power_set=power_set+[list(sub_set)+[elem]]
  return power_set

例如：

get_power_set([1,2,3])

屈服

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Answer 9

我发现以下算法非常清楚和简单：

def get_powerset(some_list):
    """Returns all subsets of size 0 - len(some_list) for some_list"""
    if len(some_list) == 0:
        return [[]]

    subsets = []
    first_element = some_list[0]
    remaining_list = some_list[1:]
    # Strategy: get all the subsets of remaining_list. For each
    # of those subsets, a full subset list will contain both
    # the original subset as well as a version of the subset
    # that contains first_element
    for partial_subset in get_all_subsets(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

生成功率集的另一种方法是生成所有具有n位的二进制数。作为幂集，带n数字的位数为2 ^ n。该算法的原理是，子集中可能存在一个元素，也可能不存在一个元素，因为二进制数字可能是一个或零，但不能同时存在。

def power_set(items):
    N = len(items)
    # enumerate the 2 ** N possible combinations
    for i in range(2 ** N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

我上MITx时发现了两种算法：6.00.2x计算思维和数据科学概论，我认为这是我所见过的最容易理解的算法之一。

Answer 10

TL; DR（直接进入简化）

我知道我以前已经添加了答案，但是我真的很喜欢我的新实现。我将一组作为输入，但是实际上它可以是任何迭代的，并且我将返回一组集合，即输入的幂集。我喜欢这种方法，因为它更符合幂集（所有子集）的数学定义。

def power_set(A):
    """A is an iterable (list, tuple, set, str, etc)
    returns a set which is the power set of A."""
    length = len(A)
    l = [a for a in A]
    ps = set()

    for i in range(2 ** length):
        selector = f'{i:0{length}b}'
        subset = {l[j] for j, bit in enumerate(selector) if bit == '1'}
        ps.add(frozenset(subset))

    return ps

如果您想要确切的答案中发布的输出，请使用以下命令：

>>> [set(s) for s in power_set({1, 2, 3, 4})]
[{3, 4},
 {2},
 {1, 4},
 {2, 3, 4},
 {2, 3},
 {1, 2, 4},
 {1, 2},
 {1, 2, 3},
 {3},
 {2, 4},
 {1},
 {1, 2, 3, 4},
 set(),
 {1, 3},
 {1, 3, 4},
 {4}]

说明

已知功率集的元素数为2 ** len(A)，因此可以在for循环中清楚地看到。

我需要将输入（最好是一组）转换为列表，因为一组是唯一无序元素的数据结构，而顺序对于生成子集至关重要。

selector是此算法的关键。请注意，selector它的长度与输入集的长度相同，为了使之成为可能，它使用带填充的f字符串。基本上，这使我可以选择在每次迭代期间将添加到每个子集的元素。假设输入集包含3个元素{0, 1, 2}，那么选择器将采用0到7（含）之间的值，二进制形式为：

000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7

因此，无论是否应添加原始集合的元素，每一位都可以用作指示符。查看二进制数字，然后将每个数字视为超集的元素，这1意味着j应添加索引处的元素，并且不应添加0该元素。

我使用集合推导在每次迭代时生成一个子集，并将此子集转换为，frozenset以便可以将其添加到ps（幂集）。否则，我将无法添加它，因为Python中的集合仅包含不可变的对象。

简化版

您可以使用一些python理解来简化代码，因此可以摆脱那些for循环。您还zip可以避免使用j索引，并且代码最终将如下所示：

def power_set(A):
    length = len(A)
    return {
        frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'})
        for i in range(2 ** length)
    }

而已。我喜欢这种算法的地方在于它比其他算法更清晰，更直观，因为itertools即使它按预期工作，依靠它看起来也很神奇。

Answer 11

我知道这已经太晚了

已经有许多其他解决方案，但仍然......

def power_set(lst):
    pw_set = [[]]

    for i in range(0,len(lst)):
        for j in range(0,len(pw_set)):
            ele = pw_set[j].copy()
            ele = ele + [lst[i]]
            pw_set = pw_set + [ele]

    return pw_set