给定一个集合
{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}]
给定一个集合
{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}]
list
而不是set
,这让我感到有点作弊。因此,出于好奇,我尝试了一个真正使用set
的简单版本,并为其他“新手Python”提供总结。Set[Set[]]
并获得包含一个空Set
的Set
,所以我最初找到它有点混淆。set
进行powerset
时,我遇到了两个问题:
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) 个 frozenset
作为输出:
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})}
set
的set
,如果你想将这些frozenset
转换为set
,你需要将它们映射回一个list
(list(map(set, powerset(set([1,2,3,4]))))
),或者修改上述内容。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']]
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
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)
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
这是我的快速实现,利用组合但仅使用内置函数。
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
这很疯狂,因为这些答案中没有一个提供实际 Python 集合的返回值。这里有一个混乱的实现,它将给出一个真正是 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([]) ])
虽然我很想看到更好的实现。
[*map(set, chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))]
;如果你喜欢,map
函数的参数可以是frozenset
。 - PM 2Ring这是我的解决方案,它在概念上与lmiguelvargasf的解决方案相似。
让我说一下 - [数学项] 根据定义,幂集包含空集 - [个人喜好] 而且我不喜欢使用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
范围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 "{}")
我之前没有接触过 more_itertools.powerset
函数,建议使用它。我还建议不要使用 itertools.combinations
的默认输出顺序,通常你想要最小化位置之间的 距离,并将子集中距离较短的项目排序放在距离较长的项目之上/之前。
itertools
recipes page 显示它使用了 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元组。如果我在旁边写上数字之间的距离(即差异),它就能表达我的观点:
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"]
,这样排列可以更清晰地说明为什么以这种顺序获取幂集可能很有用:
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)
⇣
()
(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_partitions
、print_partitions_by_length
和pprint_tuple
)。
pset_partitions.py
}}这一切都很简单,但如果您想要一些能让您直接访问幂集不同级别的代码,它仍然可能很有用:
from itertools import permutations as permute
from numpy import cumsum
# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://dev59.com/Mmkw5IYBdhLWcg3wPIJ7#5qWeEYcBWogLw_1bypnG
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://dev59.com/lW015IYBdhLWcg3w_Aug#6285330
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
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