标签归档:powerset

如何获得集合的所有子集?(电源组)

问题:如何获得集合的所有子集?(电源组)

给定一套

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

Given a set

{0, 1, 2, 3}

How can I produce the subsets:

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

回答 0

Pythonitertools页面对此有一个精确的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长度的组合。

The Python itertools page has exactly a powerset recipe for this:

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

Output:

>>> 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')]

If you don’t like that empty tuple at the beginning, you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination.


回答 1

这是有关电源组的更多代码。这是从头开始写的:

>>> 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语句更改为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意味着您无需在单个内存中计算所有结果。在主循环之外预先计算掩码被认为是值得进行的优化。

Here is more code for a powerset. This is written from scratch:

>>> 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’s comment is applicable here: “If you don’t like that empty tuple at the beginning, on.”you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination”, except in my case you change for i in range(1 << x) to for i in range(1, 1 << x).


Returning to this years later, I’d now write it like this:

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]

And then the test code would look like this, say:

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

Using yield means that you do not need to calculate all results in a single piece of memory. Precalculating the masks outside the main loop is assumed to be a worthwhile optimization.


回答 2

如果您正在寻找一个快速的答案,我刚刚在Google上搜索了“ 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]]

If you’re looking for a quick answer, I just searched “python power set” on google and came up with this: Python Power Set Generator

Here’s a copy-paste from the code in that page:

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

This can be used like this:

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

Now r is a list of all the elements you wanted, and can be sorted and printed:

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

回答 3

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

回答 4

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

There is a refinement of 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

回答 5

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即使它按预期工作,依靠它看起来也很神奇。

TL;DR (go directly to Simplification)

I know I have previously added an answer, but I really like my new implementation. I am taking a set as input, but it actually could be any iterable, and I am returning a set of sets which is the power set of the input. I like this approach because it is more aligned with the mathematical definition of power set (set of all subsets).

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

If you want exactly the output you posted in your answer use this:

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

Explanation

It is known that the number of elements of the power set is 2 ** len(A), so that could clearly be seen in the for loop.

I need to convert the input (ideally a set) into a list because by a set is a data structure of unique unordered elements, and the order will be crucial to generate the subsets.

selector is key in this algorithm. Note that selector has the same length as the input set, and to make this possible it is using an f-string with padding. Basically, this allows me to select the elements that will be added to each subset during each iteration. Let’s say the input set has 3 elements {0, 1, 2}, so selector will take values between 0 and 7 (inclusive), which in binary are:

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

So, each bit could serve as an indicator if an element of the original set should be added or not. Look at the binary numbers, and just think of each number as an element of the super set in which 1 means that an element at index j should be added, and 0 means that this element should not be added.

I am using a set comprehension to generate a subset at each iteration, and I convert this subset into a frozenset so I can add it to ps (power set). Otherwise, I won’t be able to add it because a set in Python consists only of immutable objects.

Simplification

You can simplify the code using some python comprehensions, so you can get rid of those for loops. You can also use zip to avoid using j index and the code will end up as the following:

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)
    }

That’s it. What I like of this algorithm is that is clearer and more intuitive than others because it looks quite magical to rely on itertools even though it works as expected.


回答 6

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

For example:

get_power_set([1,2,3])

yield

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

回答 7

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

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。该算法的原理是,子集中可能存在或不存在元素,因为二进制数字可能是一个或零,但不能同时存在。

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计算思维和数据科学概论,我认为这是我所见过的最容易理解的算法之一。

I have found the following algorithm very clear and simple:

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

Another way one can generate the powerset is by generating all binary numbers that have n bits. As a power set the amount of number with n digits is 2 ^ n. The principle of this algorithm is that an element could be present or not in a subset as a binary digit could be one or zero but not both.

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

I found both algorithms when I was taking MITx: 6.00.2x Introduction to Computational Thinking and Data Science, and I consider it is one of the easiest algorithms to understand I have seen.


回答 8

我只是想提供最容易理解的解决方案,即反代码高尔夫版本。

from itertools import combinations

l = ["x", "y", "z", ]

def powerset(items):
    combo = []
    for r in range(len(items) + 1):
        #use a list to coerce a actual list from the combinations generator
        combo.append(list(combinations(items,r)))
    return combo

l_powerset = powerset(l)

for i, item in enumerate(l_powerset):
    print "All sets of length ", i
    print item

结果

全部套长0

[()]

全部套长1

[('x',), ('y',), ('z',)]

全套长度2

[('x', 'y'), ('x', 'z'), ('y', 'z')]

全套长度3

[('x', 'y', 'z')]

有关更多信息,请参见itertools文档,以及有关电源集的Wikipedia条目

I just wanted to provide the most comprehensible solution, the anti code-golf version.

from itertools import combinations

l = ["x", "y", "z", ]

def powerset(items):
    combo = []
    for r in range(len(items) + 1):
        #use a list to coerce a actual list from the combinations generator
        combo.append(list(combinations(items,r)))
    return combo

l_powerset = powerset(l)

for i, item in enumerate(l_powerset):
    print "All sets of length ", i
    print item

The results

All sets of length 0

[()]

All sets of length 1

[('x',), ('y',), ('z',)]

All sets of length 2

[('x', 'y'), ('x', 'z'), ('y', 'z')]

All sets of length 3

[('x', 'y', 'z')]

For more see the itertools docs, also the wikipedia entry on power sets


回答 9

只是一个快速的动力设定刷新器!

X的幂集,简单来说就是X的所有子集的集合,包括空集

示例集X =(a,b,c)

幂集= {{a,b,c},{a,b},{a,c},{b,c},{a},{b},{c},{}}

这是查找功率集的另一种方法:

def power_set(input):
    # returns a list of all subsets of the list a
    if (len(input) == 0):
        return [[]]
    else:
        main_subset = [ ]
        for small_subset in power_set(input[1:]):
            main_subset += [small_subset]
            main_subset += [[input[0]] + small_subset]
        return main_subset

print(power_set([0,1,2,3]))

完全归功于来源

Just a quick power set refresher !

Power set of a set X, is simply the set of all subsets of X including the empty set

Example set X = (a,b,c)

Power Set = { { a , b , c } , { a , b } , { a , c } , { b , c } , { a } , { b } , { c } , { } }

Here is another way of finding power set:

def power_set(input):
    # returns a list of all subsets of the list a
    if (len(input) == 0):
        return [[]]
    else:
        main_subset = [ ]
        for small_subset in power_set(input[1:]):
            main_subset += [small_subset]
            main_subset += [[input[0]] + small_subset]
        return main_subset

print(power_set([0,1,2,3]))

full credit to source


回答 10

这可以很自然地通过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}

This can be done very naturally with 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}

回答 11

一种简单的方法是利用2的补数算法利用整数的内部表示。

整数的二进制表示形式为{000,001,010,011,100,101,110,111}对于范围从0到7的数字。对于整数计数器值,将1视为集合中包含的对应元素,将’0’视为整数作为排除,我们可以根据计数顺序生成子集。必须从生成数字0pow(2,n) -1其中n是数组的长度,即二进制表示形式的位数。

基于它的简单子集生成器函数可以编写如下。它基本上依赖

def subsets(array):
    if not array:
        return
    else:
        length = len(array)
        for max_int in range(0x1 << length):
            subset = []
            for i in range(length):
                if max_int & (0x1 << i):
                    subset.append(array[i])
            yield subset

然后可以用作

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

测验

在本地文件中添加以下内容

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

提供以下输出

Subsets for  ['b', 'd', 'f']  are  [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']]
Subsets for  ['d', 'f']  are  [[], ['d'], ['f'], ['d', 'f']]
Subsets for  ['f']  are  [[], ['f']]

A simple way would be to harness the internal representation of integers under 2’s complement arithmetic.

Binary representation of integers is as {000, 001, 010, 011, 100, 101, 110, 111} for numbers ranging from 0 to 7. For an integer counter value, considering 1 as inclusion of corresponding element in collection and ‘0’ as exclusion we can generate subsets based on the counting sequence. Numbers have to be generated from 0 to pow(2,n) -1 where n is the length of array i.e. number of bits in binary representation.

A simple Subset Generator Function based on it can be written as below. It basically relies

def subsets(array):
    if not array:
        return
    else:
        length = len(array)
        for max_int in range(0x1 << length):
            subset = []
            for i in range(length):
                if max_int & (0x1 << i):
                    subset.append(array[i])
            yield subset

and then it can be used as

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

Testing

Adding following in local file

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

gives following output

Subsets for  ['b', 'd', 'f']  are  [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']]
Subsets for  ['d', 'f']  are  [[], ['d'], ['f'], ['d', 'f']]
Subsets for  ['f']  are  [[], ['f']]

回答 12

空集是所有子集的一部分,则可以使用:

def subsets(iterable):
    for n in range(len(iterable) + 1):
        yield from combinations(iterable, n)

With empty set, which is part of all the subsets, you could use:

def subsets(iterable):
    for n in range(len(iterable) + 1):
        yield from combinations(iterable, n)

回答 13

几乎所有这些答案都使用list而不是set来代替,这对我来说似乎有点作弊。因此,出于好奇,我尝试真正地制作一个简单的版本set并为其他“ Python新手”进行总结。

我发现在处理Python的set实现方面有很多奇怪之处。给我的主要惊喜是处理空集。这与Ruby的Set实现相反,在Ruby中,我可以简单地进行操作Set[Set[]]并获得一个Set包含一个empty的内容Set,因此我最初发现它有些混乱。

回顾powerset一下,在使用sets时,我遇到了两个问题:

  1. set()需要一个可迭代的,所以set(set())会返回,set() 因为空集的可迭代是空的(我猜:)
  2. 获得一组集合,set({set()})并且set.add(set)由于不可散列而无法工作set()

为了解决这两个问题,我使用了frozenset(),这意味着我没有得到我想要的东西(类型从字面上看set),而是利用了整体set界面。

def powerset(original_set):
  # below gives us a set with one empty set in it
  ps = set({frozenset()}) 
  for member in original_set:
    subset = set()
    for m in ps:
      # to be added into subset, needs to be
      # frozenset.union(set) so it's hashable
      subset.add(m.union(set([member]))
    ps = ps.union(subset)
  return ps

下面我们frozenset正确地得到2²(16)s作为输出:

In [1]: powerset(set([1,2,3,4]))
Out[2]:
{frozenset(),
 frozenset({3, 4}),
 frozenset({2}),
 frozenset({1, 4}),
 frozenset({3}),
 frozenset({2, 3}),
 frozenset({2, 3, 4}),
 frozenset({1, 2}),
 frozenset({2, 4}),
 frozenset({1}),
 frozenset({1, 2, 4}),
 frozenset({1, 3}),
 frozenset({1, 2, 3}),
 frozenset({4}),
 frozenset({1, 3, 4}),
 frozenset({1, 2, 3, 4})}

既然没有办法有一个setset,S在Python如果你想将这些frozensets转换setS,你必须回映射到listlist(map(set, powerset(set([1,2,3,4])))) )或修改上面。

Almost all of these answers use list rather than set, which felt like a bit of a cheat to me. So, out of curiosity I tried to do a simple version truly on set and summarize for other “new to Python” folks.

I found there’s a couple oddities in dealing with Python’s set implementation. The main surprise to me was handling empty sets. This is in contrast to Ruby’s Set implementation, where I can simply do Set[Set[]] and get a Set containing one empty Set, so I found it initially a little confusing.

To review, in doing powerset with sets, I encountered two problems:

  1. set() takes an iterable, so set(set()) will return set() because the empty set iterable is empty (duh I guess :))
  2. to get a set of sets, set({set()}) and set.add(set) won’t work because set() isn’t hashable

To solve both issues, I made use of frozenset(), which means I don’t quite get what I want (type is literally set), but makes use of the overall set interace.

def powerset(original_set):
  # below gives us a set with one empty set in it
  ps = set({frozenset()}) 
  for member in original_set:
    subset = set()
    for m in ps:
      # to be added into subset, needs to be
      # frozenset.union(set) so it's hashable
      subset.add(m.union(set([member]))
    ps = ps.union(subset)
  return ps

Below we get 2² (16) frozensets correctly as output:

In [1]: powerset(set([1,2,3,4]))
Out[2]:
{frozenset(),
 frozenset({3, 4}),
 frozenset({2}),
 frozenset({1, 4}),
 frozenset({3}),
 frozenset({2, 3}),
 frozenset({2, 3, 4}),
 frozenset({1, 2}),
 frozenset({2, 4}),
 frozenset({1}),
 frozenset({1, 2, 4}),
 frozenset({1, 3}),
 frozenset({1, 2, 3}),
 frozenset({4}),
 frozenset({1, 3, 4}),
 frozenset({1, 2, 3, 4})}

As there’s no way to have a set of sets in Python, if you want to turn these frozensets into sets, you’ll have to map them back into a list (list(map(set, powerset(set([1,2,3,4])))) ) or modify the above.


回答 14

也许这个问题越来越老了,但我希望我的代码能对某人有所帮助。

def powSet(set):
    if len(set) == 0:
       return [[]]
    return addtoAll(set[0],powSet(set[1:])) + powSet(set[1:])

def addtoAll(e, set):
   for c in set:
       c.append(e)
   return set

Perhaps the question is getting old, but I hope my code will help someone.

def powSet(set):
    if len(set) == 0:
       return [[]]
    return addtoAll(set[0],powSet(set[1:])) + powSet(set[1:])

def addtoAll(e, set):
   for c in set:
       c.append(e)
   return set

回答 15

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

Use function powerset() from package more_itertools.

Yields all possible subsets of the iterable

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

If you want sets, use:

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

回答 16

递归获取所有子集。疯狂屁股一线

from typing import List

def subsets(xs: list) -> List[list]:
    return subsets(xs[1:]) + [x + [xs[0]] for x in subsets(xs[1:])] if xs else [[]]

基于Haskell解决方案

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs

Getting all the subsets with recursion. Crazy-ass one-liner

from typing import List

def subsets(xs: list) -> List[list]:
    return subsets(xs[1:]) + [x + [xs[0]] for x in subsets(xs[1:])] if xs else [[]]

Based on a Haskell solution

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs

回答 17

def findsubsets(s, n): 
    return list(itertools.combinations(s, n)) 

def allsubsets(s) :
    a = []
    for x in range(1,len(s)+1):
        a.append(map(set,findsubsets(s,x)))      
    return a
def findsubsets(s, n): 
    return list(itertools.combinations(s, n)) 

def allsubsets(s) :
    a = []
    for x in range(1,len(s)+1):
        a.append(map(set,findsubsets(s,x)))      
    return a

回答 18

您可以这样做:

def powerset(x):
    m=[]
    if not x:
        m.append(x)
    else:
        A = x[0]
        B = x[1:]
        for z in powerset(B):
            m.append(z)
            r = [A] + z
            m.append(r)
    return m

print(powerset([1, 2, 3, 4]))

输出:

[[], [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]]

You can do it like this:

def powerset(x):
    m=[]
    if not x:
        m.append(x)
    else:
        A = x[0]
        B = x[1:]
        for z in powerset(B):
            m.append(z)
            r = [A] + z
            m.append(r)
    return m

print(powerset([1, 2, 3, 4]))

Output:

[[], [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]]

回答 19

我知道这为时已晚

已经有许多其他解决方案,但仍然…

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

I know this is too late

There are many other solutions already but still…

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

回答 20

这很疯狂,因为这些答案均未提供实际的Python集的返回值。这是一个凌乱的实现,它将提供实际上是Python的powerset set

test_set = set(['yo', 'whatup', 'money'])
def powerset( base_set ):
    """ modified from pydoc's itertools recipe shown above"""
    from itertools import chain, combinations
    base_list = list( base_set )
    combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ]

    powerset = set([])
    for ll in combo_list:
        list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) 
        set_of_frozensets = set( list_of_frozensets )
        powerset = powerset.union( set_of_frozensets )

    return powerset

print powerset( test_set )
# >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']), 
#        frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']),
#        frozenset(['money','yo']), frozenset(['money']), frozenset([]) ])

不过,我希望看到更好的实现。

This is wild because none of these answers actually provide the return of an actual Python set. Here is a messy implementation that will give a powerset that actually is a Python set.

test_set = set(['yo', 'whatup', 'money'])
def powerset( base_set ):
    """ modified from pydoc's itertools recipe shown above"""
    from itertools import chain, combinations
    base_list = list( base_set )
    combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ]

    powerset = set([])
    for ll in combo_list:
        list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) 
        set_of_frozensets = set( list_of_frozensets )
        powerset = powerset.union( set_of_frozensets )

    return powerset

print powerset( test_set )
# >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']), 
#        frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']),
#        frozenset(['money','yo']), frozenset(['money']), frozenset([]) ])

I’d love to see a better implementation, though.


回答 21

这是我利用组合但仅使用内置功能的快速实现。

def powerSet(array):
    length = str(len(array))
    formatter = '{:0' + length + 'b}'
    combinations = []
    for i in xrange(2**int(length)):
        combinations.append(formatter.format(i))
    sets = set()
    currentSet = []
    for combo in combinations:
        for i,val in enumerate(combo):
            if val=='1':
                currentSet.append(array[i])
        sets.add(tuple(sorted(currentSet)))
        currentSet = []
    return sets

Here is my quick implementation utilizing combinations but using only built-ins.

def powerSet(array):
    length = str(len(array))
    formatter = '{:0' + length + 'b}'
    combinations = []
    for i in xrange(2**int(length)):
        combinations.append(formatter.format(i))
    sets = set()
    currentSet = []
    for combo in combinations:
        for i,val in enumerate(combo):
            if val=='1':
                currentSet.append(array[i])
        sets.add(tuple(sorted(currentSet)))
        currentSet = []
    return sets

回答 22

范围n中的所有子集均已设置:

n = int(input())
l = [i for i in range (1, n + 1)]

for number in range(2 ** n) :
    binary = bin(number)[: 1 : -1]
    subset = [l[i] for i in range(len(binary)) if binary[i] == "1"]
    print(set(sorted(subset)) if number > 0 else "{}")

All subsets in range n as set:

n = int(input())
l = [i for i in range (1, n + 1)]

for number in range(2 ** n) :
    binary = bin(number)[: 1 : -1]
    subset = [l[i] for i in range(len(binary)) if binary[i] == "1"]
    print(set(sorted(subset)) if number > 0 else "{}")

回答 23

import math    
def printPowerSet(set,set_size): 
    pow_set_size =int(math.pow(2, set_size))
    for counter in range(pow_set_size):
    for j in range(set_size):  
        if((counter & (1 << j)) > 0):
            print(set[j], end = "")
    print("")
set = ['a', 'b', 'c']
printPowerSet(set,3)
import math    
def printPowerSet(set,set_size): 
    pow_set_size =int(math.pow(2, set_size))
    for counter in range(pow_set_size):
    for j in range(set_size):  
        if((counter & (1 << j)) > 0):
            print(set[j], end = "")
    print("")
set = ['a', 'b', 'c']
printPowerSet(set,3)

回答 24

我在《发现计算机科学:跨学科问题,原理和Python编程。2015年版》这本书中看到了一个问题的变体。在练习10.2.11中,输入只是一个整数,而输出应为幂集。这是我的递归解决方案(除了基本的python3,不使用其他任何东西)

def powerSetR(n):
    assert n >= 0
    if n == 0:
        return [[]]
    else:
        input_set = list(range(1, n+1)) # [1,2,...n]
        main_subset = [ ]
        for small_subset in powerSetR(n-1):
            main_subset += [small_subset]
            main_subset += [ [input_set[-1]] + small_subset]
        return main_subset

superset = powerSetR(4)
print(superset)       
print("Number of sublists:", len(superset))

输出是

[[],[4],[3],[4、3],[2],[4、2],[3、2],[4、3、2],[1],[4、1 ],[3、1],[4、3、1],[2、1],[4、2、1],[3、2、1],[4、3、2、1]]的数量子列表:16

A variation of the question, is an exercise I see on the book “Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming. 2015 edition”. In that exercise 10.2.11, the input is just an integer number, and the output should be the power sets. Here is my recursive solution (not using anything else but basic python3 )

def powerSetR(n):
    assert n >= 0
    if n == 0:
        return [[]]
    else:
        input_set = list(range(1, n+1)) # [1,2,...n]
        main_subset = [ ]
        for small_subset in powerSetR(n-1):
            main_subset += [small_subset]
            main_subset += [ [input_set[-1]] + small_subset]
        return main_subset

superset = powerSetR(4)
print(superset)       
print("Number of sublists:", len(superset))

And the output is

[[], [4], [3], [4, 3], [2], [4, 2], [3, 2], [4, 3, 2], [1], [4, 1], [3, 1], [4, 3, 1], [2, 1], [4, 2, 1], [3, 2, 1], [4, 3, 2, 1]] Number of sublists: 16


回答 25

我没有遇到过该more_itertools.powerset功能,建议使用它。我还建议不要使用的默认输出顺序itertools.combinations,通常是希望最小化位置之间的距离,并对位置之间距离较短的项目子集进行排序,使其高于/之间距离更大的项目。

itertools食谱页面显示它使用chain.from_iterable

  • 请注意,r这里与二项式系数的下部的标准符号匹配,s通常n在数学课本和计算器中称为“ n选择r”
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))

这里的其他示例[1,2,3,4]以2个元组以“字典顺序”的顺序列出(当我们将数字打印为整数时)给出的幂集。如果我在旁边写上数字之间的距离(即差),它表明了我的观点:

121
132
143
231
242
341

子集的正确顺序应该是首先“耗尽”最小距离的顺序,如下所示:

121
231
341
132
242
143

在这里使用数字会使此顺序看起来“错误”,但是考虑一下字母,["a","b","c","d"]这很清楚为什么对于按此顺序获得幂集可能很有​​用:

ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3

对于更多项目,此效果更加明显,就我的目的而言,它使能够有意义地描述Powerset的索引范围之间有所不同。

(关于组合代码中算法的输出顺序,有很多关于格雷码等的文章,我不认为这是附带问题)。

我实际上只是编写了一个相当复杂的程序,该程序使用此快速整数分区代码以正确的顺序输出值,但是随后我发现more_itertools.powerset并且对于大多数使用方法而言,仅使用该函数就可以了,就像这样:

from more_itertools import powerset
from numpy import ediff1d

def ps_sorter(tup):
    l = len(tup)
    d = ediff1d(tup).tolist()
    return l, d

ps = powerset([1,2,3,4])

ps = sorted(ps, key=ps_sorter)

for x in ps:
    print(x)

()
(1,)
(2,)
(3,)
(4,)
(1, 2)
(2, 3)
(3, 4)
(1, 3)
(2, 4)
(1, 4)
(1, 2, 3)
(2, 3, 4)
(1, 2, 4)
(1, 3, 4)
(1, 2, 3, 4)

我写了一些更复杂的代码,这将很好地打印幂(见回购了漂亮的印刷,我这里不包括的功能:print_partitionsprint_partitions_by_length,和pprint_tuple)。

这一切都非常简单,但是如果您想要一些可以直接访问不同级别的Powerset的代码,它可能仍然有用:

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# /programming/10035752/elegant-python-code-for-integer-partitioning#comment25080713_10036764

def asc_int_partitions(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield tuple(a[:k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[:k + 1])

# https://stackoverflow.com/a/6285330/2668831
def uniquely_permute(iterable, enforce_sort=False, r=None):
    previous = tuple()
    if enforce_sort: # potential waste of effort (default: False)
        iterable = sorted(iterable)
    for p in permute(iterable, r):
        if p > previous:
            previous = p
            yield p

def sum_min(p):
    return sum(p), min(p)

def partitions_by_length(max_n, sorting=True, permuting=False):
    partition_dict = {0: ()}
    for n in range(1,max_n+1):
        partition_dict.setdefault(n, [])
        partitions = list(asc_int_partitions(n))
        for p in partitions:
            if permuting:
                perms = uniquely_permute(p)
                for perm in perms:
                    partition_dict.get(len(p)).append(perm)
            else:
                partition_dict.get(len(p)).append(p)
    if not sorting:
        return partition_dict
    for k in partition_dict:
        partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
    return partition_dict

def print_partitions_by_length(max_n, sorting=True, permuting=True):
    partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
    for k in partition_dict:
        if k == 0:
            print(tuple(partition_dict.get(k)), end="")
        for p in partition_dict.get(k):
            print(pprint_tuple(p), end=" ")
        print()
    return

def generate_powerset(items, subset_handler=tuple, verbose=False):
    """
    Generate the powerset of an iterable `items`.

    Handling of the elements of the iterable is by whichever function is passed as
    `subset_handler`, which must be able to handle the `None` value for the
    empty set. The function `string_handler` will join the elements of the subset
    with the empty string (useful when `items` is an iterable of `str` variables).
    """
    ps = {0: [subset_handler()]}
    n = len(items)
    p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
    for p_len, parts in p_dict.items():
        ps.setdefault(p_len, [])
        if p_len == 0:
            # singletons
            for offset in range(n):
                subset = subset_handler([items[offset]])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        for pcount, partition in enumerate(parts):
            distance = sum(partition)
            indices = (cumsum(partition)).tolist()
            for offset in range(n - distance):
                subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - distance - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        if verbose and p_len < n-1:
            print()
    return ps

作为示例,我编写了一个CLI演示程序,该程序将字符串作为命令行参数:

python string_powerset.py abcdef

a, b, c, d, e, f

ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af

abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf

abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef

abcde, bcdef
abcdf
abcef
abdef
acdef

abcdef

I hadn’t come across the more_itertools.powerset function and would recommend using that. I also recommend not using the default ordering of the output from itertools.combinations, often instead you want to minimise the distance between the positions and sort the subsets of items with shorter distance between them above/before the items with larger distance between them.

The itertools recipes page shows it uses chain.from_iterable

  • Note that the r here matches the standard notation for the lower part of a binomial coefficient, the s is usually referred to as n in mathematics texts and on calculators (“n Choose r”)
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))

The other examples here give the powerset of [1,2,3,4] in such a way that the 2-tuples are listed in “lexicographic” order (when we print the numbers as integers). If I write the distance between the numbers alongside it (i.e. the difference), it shows my point:

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

The correct order for subsets should be the order which ‘exhausts’ the minimal distance first, like so:

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

Using numbers here makes this ordering look ‘wrong’, but consider for example the letters ["a","b","c","d"] it is clearer why this might be useful to obtain the powerset in this order:

ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3

This effect is more pronounced with more items, and for my purposes it makes the difference between being able to describe the ranges of the indexes of the powerset meaningfully.

(There is a lot written on Gray codes etc. for the output order of algorithms in combinatorics, I don’t see it as a side issue).

I actually just wrote a fairly involved program which used this fast integer partition code to output the values in the proper order, but then I discovered more_itertools.powerset and for most uses it’s probably fine to just use that function like so:

from more_itertools import powerset
from numpy import ediff1d

def ps_sorter(tup):
    l = len(tup)
    d = ediff1d(tup).tolist()
    return l, d

ps = powerset([1,2,3,4])

ps = sorted(ps, key=ps_sorter)

for x in ps:
    print(x)

()
(1,)
(2,)
(3,)
(4,)
(1, 2)
(2, 3)
(3, 4)
(1, 3)
(2, 4)
(1, 4)
(1, 2, 3)
(2, 3, 4)
(1, 2, 4)
(1, 3, 4)
(1, 2, 3, 4)

I wrote some more involved code which will print the powerset nicely (see the repo for pretty printing functions I’ve not included here: print_partitions, print_partitions_by_length, and pprint_tuple).

This is all pretty simple, but still might be useful if you want some code that’ll let you get straight to accessing the different levels of the powerset:

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning#comment25080713_10036764

def asc_int_partitions(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield tuple(a[:k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[:k + 1])

# https://stackoverflow.com/a/6285330/2668831
def uniquely_permute(iterable, enforce_sort=False, r=None):
    previous = tuple()
    if enforce_sort: # potential waste of effort (default: False)
        iterable = sorted(iterable)
    for p in permute(iterable, r):
        if p > previous:
            previous = p
            yield p

def sum_min(p):
    return sum(p), min(p)

def partitions_by_length(max_n, sorting=True, permuting=False):
    partition_dict = {0: ()}
    for n in range(1,max_n+1):
        partition_dict.setdefault(n, [])
        partitions = list(asc_int_partitions(n))
        for p in partitions:
            if permuting:
                perms = uniquely_permute(p)
                for perm in perms:
                    partition_dict.get(len(p)).append(perm)
            else:
                partition_dict.get(len(p)).append(p)
    if not sorting:
        return partition_dict
    for k in partition_dict:
        partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
    return partition_dict

def print_partitions_by_length(max_n, sorting=True, permuting=True):
    partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
    for k in partition_dict:
        if k == 0:
            print(tuple(partition_dict.get(k)), end="")
        for p in partition_dict.get(k):
            print(pprint_tuple(p), end=" ")
        print()
    return

def generate_powerset(items, subset_handler=tuple, verbose=False):
    """
    Generate the powerset of an iterable `items`.

    Handling of the elements of the iterable is by whichever function is passed as
    `subset_handler`, which must be able to handle the `None` value for the
    empty set. The function `string_handler` will join the elements of the subset
    with the empty string (useful when `items` is an iterable of `str` variables).
    """
    ps = {0: [subset_handler()]}
    n = len(items)
    p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
    for p_len, parts in p_dict.items():
        ps.setdefault(p_len, [])
        if p_len == 0:
            # singletons
            for offset in range(n):
                subset = subset_handler([items[offset]])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        for pcount, partition in enumerate(parts):
            distance = sum(partition)
            indices = (cumsum(partition)).tolist()
            for offset in range(n - distance):
                subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - distance - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        if verbose and p_len < n-1:
            print()
    return ps

As an example, I wrote a CLI demo program which takes a string as a command line argument:

python string_powerset.py abcdef

a, b, c, d, e, f

ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af

abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf

abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef

abcde, bcdef
abcdf
abcef
abdef
acdef

abcdef

回答 26

如果您想要任何特定长度的子集,可以这样操作:

from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])

通常,对于任意长度的子集,您可以修改范围偏差。输出是

[(),(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 )]

If you want any specific length of subsets you can do it like this:

from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])

More generally for arbitary length subsets you can modify the range arugment. The output is

[(), (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)]


回答 27

def powerset(some_set):
    res = [(a,b) for a in some_set for b in some_set]
    return res
def powerset(some_set):
    res = [(a,b) for a in some_set for b in some_set]
    return res