Как получить все подмножества набора? (степенное множество)
Joe, я предлагаю, чтобы Вы исследовали IKVM. Вы могли бы найти что-то там, которое царапает Ваш зуд
4 ответа
Страница 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.
def powerset(lst):
return reduce(lambda result, x: result + [subset + [x] for subset in result],
lst, [[]])
Если вы ищете быстрый ответ, я просто искал «питон питона» в Google и нашел это: генератор питающей установки питона
вот копия- вставьте из кода на этой странице:
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]]
Вот еще код для набора мощности. Это написано с нуля:
>>> 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]
Комментарий Марка Рушакова применим здесь: «Если вам не нравится этот пустой кортеж в начале, дальше», вы можете просто изменить оператор диапазона на range (1, len (s) + 1) чтобы избежать комбинации длины 0 », за исключением того, что в моем случае вы меняете для i в диапазоне (1 << x) на для i в диапазоне (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 означает, что вы нет необходимости вычислять все результаты в одном фрагменте памяти. Предполагается, что предварительное вычисление масок вне основного цикла будет стоящей оптимизацией.