如何获取一个集合的所有子集？（幂集）

Question

如何获取一个集合的所有子集？（幂集）

202

给定一个集合

{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}]

- patrick

@X10D 很多。例如：https://scholar.google.com/scholar?start=40&q=power+sets&hl=en&as_sdt=0,5 - Alexandre Huat

3

对于基于约束的因果发现算法，需要通过对所有涉及变量的可能子集进行条件独立性检验。我还遇到了在计算布尔函数的傅里叶级数时需要使用幂集。这显然只是冰山一角。 - Nazaal

2

@X10D 询问幂集的应用就像询问子集的应用一样，这是一个基本的数学概念。如何使用它取决于您。我曾尝试过使用它来尝试各种事物的组合。假设您的集合包含动作，您想测试所有可能的动作子集。那么迭代幂集就会感觉很自然。 - DustByte

32个回答

83

这里是更多的幂集代码。这是从零开始编写的：

>>> 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的评论适用于这里：“如果你不喜欢在开头有空元组，那么可以将范围语句更改为range(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 意味着您不需要在单个内存块中计算所有结果。外部预先计算掩码被认为是一种值得优化的方式。

- hughdbrown

9

这是一个有创意的答案。但是，我用 timeit 测量它并将其与 Mark Rushakoff 进行比较，发现它明显更慢。为了生成 16 个项目的幂集 100 次，我的测量结果为 0.55 秒，而 Rushakoff 的测量结果为 15.6 秒。 - Ceasar

你如何处理重复数据？ - llamaro25

任何Python中的重复问题都可以使用set()解决。 - Innomight

1

@CeasarBautista 你不能将用户函数与内置函数进行比较。内置函数总是在可能的情况下进行了优化。 - lxg95

@lxg95你说的“不能比较”是什么意思？如果不进行比较，那你怎么决定选择哪一个呢？ - Alexandre Huat

27

如果您正在寻找快速答案，我刚在谷歌上搜索了“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]]

- Edan Maor

3

如果输入的是空数组，上述代码将返回 [[][]]，为了解决这个问题，需要分别处理长度检查的情况： if len(seq) == 0: yield [] else if len(seq) == 1: yield seq yield [] - Ayush

3

参考资料，我使用 timeit 进行了测量，并将其与 Mark Rushakoff 的答案中的 powerset 食谱进行了比较。在我的电脑上，对于生成 16 个项目的幂集 100 次，这个算法花费了 1.36 秒，而 Rushakoff 的算法花费了 0.55 秒。 - Ceasar

这个的时间复杂度是多少？ - CodeQuestor

@CodeQuestor 我评估了复制粘贴部分的时间复杂度。对我来说，它感觉像是O(n^2)。for循环贡献了1个n，递归调用贡献了n-1。因此，总共变成了O(n^2)。除此之外，如果我们考虑调用powerset(l)的外部循环，另一个n将与前面的结果相乘，使其变为O(n^3)。我是一个初学者和学生。所以如果我的观点有误，请纠正我。保持安全。 - MANEESH MOHAN

16

使用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)))

- Alexandre Huat

4

这里有很多人在重复造轮子，我认为这个答案是最好的，因为它可能已经包含在您的依赖项中，因为许多常用库（例如pytest）需要它。https://libraries.io/pypi/more-itertools/dependents - Karl Lorey

2

引入依赖项来处理三行代码并不总是明智的选择。 - Paul Crowley

1

三行代码？你是指在 itertools 中给出的实现吗？
这样轻量级的包是否会成为一个问题依赖项？

- Alexandre Huat

13

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

- newacct

你应该添加 from functools import reduce。 - parvij

13

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

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_powerset(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

生成幂集的另一种方法是生成所有具有 n 位的二进制数。作为幂集，具有 n 位数字的数量是 2 ^ n。该算法的原则是一个元素可以存在于子集中，也可以不存在；正如二进制数字可以是 1 或 0，但不能同时为两者。

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计算思维和数据科学导论时，了解了这两种算法。我认为这是我见过最容易理解的算法之一。

- lmiguelvargasf

11

简化版

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

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之间（包括0和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 这个神奇的工具，即使它按预期工作。

- lmiguelvargasf

1

这基本上是与此前的答案 https://dev59.com/m3M_5IYBdhLWcg3wMgEF#1482320 相同的想法。 - tomasz

11

有一种幂集的改进：

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

- Jingguo Yao

7

这可以通过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}

- Paul Crowley

2

这个问题得到的最优雅的答案 - Arthur B.

@ArthurB。https://dev59.com/m3M_5IYBdhLWcg3wMgEF#59883397 - Alexandre Huat

2

似乎不仅是最优雅的，而且速度也快得多，相差很大。请查看此线程中的“timeit”。https://gist.github.com/ciphergoth/22569ed316a61e40f7ef49f986e9704f - Paul Crowley

7

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 to it
      # effectively doubling the sets resulting in the 2^n sets in the powerset of s.
      power_set=power_set+[list(sub_set)+[elem]]
  return power_set

例如：

get_power_set([1,2,3])

yield

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

- jmkg

3

在控制循环的循环变量（power_set）中修改它是一种非常可疑的做法。例如，假设您编写了以下代码而不是建议的变量修改代码：power_set += [list(sub_set)+[elem]]。那么循环将无法终止。 - hughdbrown

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Rushakoff · Accepted Answer

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 的组合。