Ответ 1

Страница 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 длинами.

Ответ 2

Вот еще код для poweret. Это написано с нуля:

>>> 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 применим здесь: "Если вам не нравится этот пустой кортеж в начале, вкл.", вы можете просто изменить оператор диапазона на диапазон (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 означает, что вам не нужно вычислять все результаты в одной части памяти. Предполагается, что предварительное вычисление масок вне основного цикла является стоящей оптимизацией.

Ответ 3

Если вы ищете быстрый ответ, я просто искал "power power set" на google и придумал это: Генератор Power Set Python

Здесь скопируйте пасту из кода на этой странице:

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

Ответ 4

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

Ответ 5

Существует уточнение набора параметров:

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

Ответ 6

Я нашел следующий алгоритм очень понятным и понятным:

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

Другим способом генерации силового набора является создание всех двоичных чисел с битами 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 Введение в вычислительное мышление и науку о данных, и я считаю, что это один из самых простых алгоритмов, которые я понял.

Ответ 7

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

Ответ 8

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 даже если он работает как ожидалось.

Ответ 9

Просто быстрое обновление питания!

Набор мощности набора 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]))

полный кредит на источник

Ответ 10

Я просто хотел предоставить наиболее приемлемое решение - версию с кодом для кодов.

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 на power наборы

Ответ 11

Почти во всех этих ответах используется list, а не set, что мне показалось немного обманным. Поэтому из любопытства я попытался действительно сделать простую версию set и подвести итог для других людей, "новичков в Python".

Я обнаружил там пару странностей в работе с реализацией Python. Главным сюрпризом для меня была обработка пустых наборов. Это в отличие от реализации Ruba Set, где я могу просто сделать Set[Set[]] и получить Set, содержащий одну пустую Set, поэтому я нахожу это сначала немного запутанным.

Чтобы проверить, при работе powerset с set я столкнулся с двумя проблемами:

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

Поскольку в Python невозможно иметь set из set, если вы хотите превратить эти frozenset в set s, вам придется отобразить их обратно в list (list(map(set, powerset(set([1,2,3,4])))) ) или измените вышесказанное.

Ответ 12

Это дико, потому что ни один из этих ответов не обеспечивает возврат фактического набора Python. Вот беспорядочная реализация, которая даст набор полномочий, который на самом деле является Python set.

test_set = set(['yo', 'whatup', 'money'])
def powerset( base_set ):
    """ modified from pydoc 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([]) ])

Мне бы хотелось увидеть лучшую реализацию.

Ответ 13

Вот моя быстрая реализация с использованием комбинаций, но с использованием только встроенных модулей.

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

Ответ 14

Простой способ состоит в том, чтобы использовать внутреннее представление целых чисел в 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']]

Ответ 15

В Python 3.5 или выше вы можете использовать оператор yield from вместе с itertools.combination:

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

Ответ 16

С пустым набором, который является частью всех подмножеств, вы можете использовать:

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

Ответ 17

Возможно, вопрос стареет, но я надеюсь, что мой код кому-нибудь поможет.

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

Ответ 18

"""
    from https://docs.python.org/3.6/library/itertools.html
    uses the module itertools
    chaining together the two functions combinations() and chain() is faster
    than iterating and generator functions in Python

    Author: joltE
    Date: 3/15/2017
"""
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    from itertools import chain, combinations 
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def AllCombo(items):
    return [list(i) for i in powerset(items)]

испытательный стенд

print(AllCombo([1, 3, 5, 7]))
print([list(i) for i in powerset([1, 3, 5, 7])])

powerset() действует как функция генератора, но более эффективна благодаря использованию только встроенных функций itertools chain() и комбинаций(). powerset() выводит кортежи, это можно преобразовать в списки, как это было сделано в AllCombo со списком(). Оба оператора печати в тестовом стенде выводят те же данные.