给定一个集合
{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}]
问问题
174058 次
30 回答
218
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 长度组合。
于 2009-09-26T22:18:15.053 回答
71
这里有更多关于 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 的评论适用于此处：“如果您不喜欢开头的那个空元组，请打开。”您可以将 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意味着您不需要在一块内存中计算所有结果。在主循环之外预先计算掩码被认为是值得优化的。
于 2009-09-26T22:20:22.150 回答
22
如果你正在寻找一个快速的答案，我刚刚在谷歌上搜索了“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]]
于 2009-09-26T22:21:05.987 回答
13
def powerset(lst):
return reduce(lambda result, x: result + [subset + [x] for subset in result],
lst, [[]])
于 2009-09-26T22:54:12.663 回答
12
我发现以下算法非常清晰和简单：
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 Introduction to Computational Thinking and Data Science 时发现了这两种算法，我认为这是我见过的最容易理解的算法之一。
于 2017-03-11T18:57:43.110 回答
11
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
于 2013-09-29T13:43:39.570 回答
11
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意味着不应该添加该元素。
我使用集合推导在每次迭代中生成一个子集，并将这个子集转换为 a 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即使它按预期工作。
于 2019-04-03T04:29:25.483 回答
5
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]]
于 2013-07-17T12:40:08.030 回答
5
我知道这为时已晚
已经有许多其他解决方案，但仍然......
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
于 2020-10-18T09:05:20.000 回答
5
这可以很自然地完成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}
于 2020-10-12T15:13:30.893 回答
5
使用powerset()package中的函数more_itertools。
产生可迭代的所有可能子集
>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
如果你想要套装，请使用：
list(map(set, powerset(iterable)))
于 2020-01-23T16:44:00.780 回答
3
我只是想提供最容易理解的解决方案，anti code-golf 版本。
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 文档，以及关于power set的维基百科条目
于 2013-02-16T03:56:58.790 回答
3
对于作为所有子集的一部分的空集，您可以使用：
def subsets(iterable):
for n in range(len(iterable) + 1):
yield from combinations(iterable, n)
于 2019-06-25T11:56:43.137 回答
2
如果您想要任何特定长度的子集，您可以这样做：
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 )]
于 2020-08-12T05:57:20.790 回答
2
from itertools import combinations
def subsets(arr: set) -> list:
subsets = []
[subsets.extend(list(combinations(arr,n))) for n in range(len(arr))]
return subsets
a = {1,2,3}
print(subsets(a))
输出：
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3)]
对于排序的子集，我们可以这样做：
# sorted subsets
print(sorted(subsets(a)))
输出：
[(), (1,), (1, 2), (1, 3), (2,), (2, 3), (3,)]
于 2021-11-18T15:25:28.473 回答
2
只是一个快速的电源组复习！
集合 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]))
完全归功于来源
于 2019-01-15T07:45:46.157 回答
1
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
于 2020-03-23T00:24:37.750 回答
1
几乎所有这些答案都使用list而不是set，这对我来说有点欺骗。因此，出于好奇，我尝试真正做一个简单的版本，set并为其他“Python 新手”做总结。
我发现在处理 Python 的set implementation时有一些奇怪的地方。对我来说主要的惊喜是处理空集。这与 Ruby 的Set 实现形成对比，我可以简单地做Set[Set[]]一个Set包含一个空的Set，所以我最初发现它有点混乱。
回顾一下，在powerset用sets做的时候，遇到了两个问题：
set()需要一个可迭代的，所以set(set())会返回set()，因为空集可迭代是空的（呃，我猜 :)）- 获得一组集合，
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
下面我们正确地得到 2² (16) frozensets 作为输出：
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})}
由于 Python 中没有 a setof sets，如果你想将这些frozensets 变成sets，你必须将它们映射回 a list( list(map(set, powerset(set([1,2,3,4]))))
) 或修改上面的。
于 2019-07-28T18:40:20.480 回答
1
也许问题已经过时了，但我希望我的代码能对某人有所帮助。
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
于 2019-09-26T02:40:06.203 回答
1
使用递归获取所有子集。疯狂的单线
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
于 2020-03-22T09:38:50.163 回答
1
你可以这样做：
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]]
于 2020-09-10T20:14:06.490 回答
1
一种简单的方法是利用 2 的补码算法下的整数的内部表示。
对于从 0 到 7 的数字，整数的二进制表示为 {000, 001, 010, 011, 100, 101, 110, 111}。对于整数计数器值，将 1 视为包含相应元素的集合和“0”作为排除，我们可以根据计数序列生成子集。必须从0到生成数字，pow(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']]
于 2019-01-21T11:01:52.350 回答
0
这很疯狂，因为这些答案都没有真正提供实际 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([]) ])
不过，我希望看到更好的实现。
于 2013-04-11T06:43:45.613 回答
0
这是我使用组合但仅使用内置插件的快速实现。
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
于 2013-09-20T23:06:30.973 回答
0
范围 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 "{}")
于 2020-03-24T13:44:41.377 回答
0
这是我的解决方案，它（在概念上）与 lmiuelvargasf 的解决方案相似。
让我说 -[math item] 根据定义，powerset 确实包含空集 -[personal taste]，而且我不喜欢使用frozenset。
所以输入是一个列表，输出是一个列表。该函数可以提前关闭，但我喜欢按字典顺序排列的幂集元素，这基本上意味着很好。
def power_set(L):
"""
L is a list.
The function returns the power set, but as a list of lists.
"""
cardinality=len(L)
n=2 ** cardinality
powerset = []
for i in range(n):
a=bin(i)[2:]
subset=[]
for j in range(len(a)):
if a[-j-1]=='1':
subset.append(L[j])
powerset.append(subset)
#the function could stop here closing with
#return powerset
powerset_orderred=[]
for k in range(cardinality+1):
for w in powerset:
if len(w)==k:
powerset_orderred.append(w)
return powerset_orderred
于 2020-12-11T16:28:45.357 回答
0
这个问题的一个变体是我在“发现计算机科学：跨学科问题、原则和 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
于 2020-04-03T21:06:05.427 回答
0
我没有遇到过这个more_itertools.powerset功能，建议使用它。我还建议不要使用来自 的输出的默认排序itertools.combinations，通常您希望最小化位置之间的距离，并对它们之间距离较短的项目子集在它们之间距离较大的项目之上/之前进行排序。
itertools食谱页面显示它使用chain.from_iterable
- 请注意，这里与二项式系数
r下半部分的标准表示法相匹配，通常在数学课本和计算器中被称为（“n 选择 r”）sn
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 元组以“字典”顺序列出（当我们将数字打印为整数时）。如果我在旁边写下数字之间的距离（即差异），它说明了我的观点：
12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1
子集的正确顺序应该是首先“耗尽”最小距离的顺序，如下所示：
12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3
在这里使用数字会使这个排序看起来“错误”，但是考虑例如字母["a","b","c","d"]更清楚为什么这可能有助于按此顺序获取 powerset：
ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3
这种效果在项目越多时越明显，就我的目的而言，它使得能够有意义地描述幂集的索引范围有所不同。
（关于组合算法的输出顺序有很多关于格雷码等的文章，我不认为这是一个附带问题）。
我实际上只是写了一个相当复杂的程序，它使用这个快速整数分区代码以正确的顺序输出值，但后来我发现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)
⇣</p>
()
(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)
我编写了一些更复杂的代码，它们可以很好地打印 powerset（请参阅 repo 以了解我在这里没有包含的漂亮打印功能：print_partitions、、print_partitions_by_length和pprint_tuple）。
这一切都非常简单，但如果您想要一些可以让您直接访问不同级别的 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
例如，我编写了一个 CLI 演示程序，它将字符串作为命令行参数：
python string_powerset.py abcdef
⇣</p>
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
于 2020-06-22T18:56:42.120 回答
0
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)
于 2020-03-27T09:06:15.163 回答
-2
def powerset(some_set):
res = [(a,b) for a in some_set for b in some_set]
return res
于 2020-11-06T15:38:10.267 回答