Как получить все подмножества набора? (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}]
34 ответа
Питон itertools страница имеет ровно powerset рецепт для этого:
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-длины.
Вот еще код для 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]
Комментарий Марка Рушакова применим здесь: "Если вам не нравится этот пустой кортеж в начале, вкл.", Вы можете просто изменить выражение диапазона на 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 означает, что вам не нужно вычислять все результаты в одном фрагменте памяти. Предполагается, что предварительный расчет масок вне основного цикла является полезной оптимизацией.
Если вы ищете быстрый ответ, я просто поискал "python power set" в Google и придумал следующее: 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]]
Функция использования 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)))
def powerset(lst):
return reduce(lambda result, x: result + [subset + [x] for subset in result],
lst, [[]])
Я нашел следующий алгоритм очень ясным и простым:
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_all_subsets(remaining_list):
subsets.append(partial_subset)
subsets.append(partial_subset[:] + [first_element])
return subsets
Другой способ генерировать powerset - это генерировать все двоичные числа, которые имеют 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 Введение в вычислительное мышление и науку о данных, и считаю, что это один из самых простых алгоритмов для понимания, который я видел.
Есть доработка 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
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, так что вы можете избавиться от них для циклов. Вы также можете использовать 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 хотя он работает как ожидалось.
Это можно сделать очень естественно с помощью
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}
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 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
Я просто хотел предложить наиболее приемлемое решение, анти-код-версию для гольфа.
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, а также статью в Википедии о комплектах питания
С пустым набором, который является частью всех подмножеств, вы можете использовать:
def subsets(iterable):
for n in range(len(iterable) + 1):
yield from combinations(iterable, n)
def powerSet(s):
sets = [[]]
for i in s:
newsets = []
for k in sets:
newsets.append(k+[i])
sets += newsets
return sets
Код сначала, для тех, кто хочет простой ответ. У меня есть хорошее объяснение здесь https://leetcode.com/problems/subsets/solutions/3138042/simple-python-solution/
Но краткий ответ заключается в том, что вы начинаете с набора пустого набора, т.е. "sets = [[]]". Я рекомендую поместить оператор печати в разделе «для i в s», то есть «распечатать (наборы)», и увидеть, что он удваивается для каждого элемента i.
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,)]
Если вам нужна определенная длина подмножеств, вы можете сделать это следующим образом:
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))]
Сделать это можно так:
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]]
Просто быстрое обновление питания!
Набор мощности набора X, это просто набор всех подмножеств X, включая пустой набор
Пример набора X = (a, b, c)
Power Set = {{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]))
полный кредит на источник
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
Почти все эти ответы используют list скорее, чем set, что показалось мне немного обманом. Итак, из любопытства я попытался сделать простую версию действительно наset и подведем итоги для других "новичков в Python".
Я обнаружил, что при работе с реализацией набора Python есть несколько странностей. Основным сюрпризом для меня стало обращение с пустыми наборами. Это контрастирует с реализацией Set в Ruby, где я могу просто сделать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})}
Поскольку нет возможности иметь set из sets в Python, если вы хотите включить эти frozensetс в sets, вам придется отобразить их обратно в list (list(map(set, powerset(set([1,2,3,4]))))
) или измените указанное выше.
Простой способ - использовать внутреннее представление целых чисел в арифметике дополнения до 2.
Двоичное представление целых чисел: {000, 001, 010, 011, 100, 101, 110, 111} для чисел в диапазоне от 0 до 7. Для значения счетчика целых чисел, рассматривая 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']]
Возможно, вопрос устаревает, но я надеюсь, что мой код кому-то поможет.
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
Получение всех подмножеств с помощью рекурсии. Сумасшедший однострочный
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
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)
Вариант вопроса - это упражнение, которое я вижу в книге "Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming. Edition 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
Это дико, потому что ни один из этих ответов фактически не обеспечивает возвращение фактического набора Python. Вот грязная реализация, которая даст powerset, который на самом деле является 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([]) ])
Я хотел бы видеть лучшую реализацию, все же.
Все подмножества в диапазоне 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страница рецептов показывает, что он используетchain.from_iterable
- Обратите внимание, что
rздесь соответствует стандартным обозначениям для нижней части биномиального коэффициента,sобычно упоминается как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)
Я написал более сложный код, который будет красиво печатать powerset (см. Репозиторий для красивых функций печати, которые я здесь не включил: print_partitions, print_partitions_by_length, а также pprint_tuple).
- Репо: заказанный набор мощности, в частности
pset_partitions.py
Все это довольно просто, но все же может быть полезно, если вам нужен какой-то код, который позволит вам сразу получить доступ к различным уровням powerset:
from itertools import permutations as permute
from numpy import cumsum
# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://stackru.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://stackru.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
Вот моя быстрая реализация с использованием комбинаций, но с использованием только встроенных модулей.
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
#Надеюсь, это сработает для вас
ab=['a','b', 'c']
for i in range(2**len(ab)):
for j in range(len(ab)):
if '1' in bin(i)[-1:-4:-1][j]:
print(ab[j], end=" ")
print()