Biorąc pod uwagę zestaw

{0, 1, 2, 3}

Jak mogę utworzyć podzbiory:

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

Python itertoolsstrona ma dokładnie to powersetprzepis na to:

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

Wynik:

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

Jeśli nie podoba ci się ta pusta krotka na początku, możesz po prostu zmienić rangeinstrukcję na, range(1, len(s)+1)aby uniknąć kombinacji o długości 0.

Tutaj jest więcej kodu dla PowerSet. To jest napisane od podstaw:

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

Komentarz Marka Rushakoffa ma tutaj zastosowanie: „Jeśli nie podoba ci się ta pusta krotka na początku, on.” Możesz po prostu zmienić instrukcję zakresu na zakres (1, len (s) +1), aby uniknąć kombinacji o długości 0 ”, z wyjątkiem mojego przypadku, gdy zmienisz for i in range(1 << x)na for i in range(1, 1 << x).

Wracając do tego lata później, teraz napisałbym to tak:

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]

Następnie kod testowy wyglądałby następująco:

print(list(powerset([4, 5, 6])))

Używanie yieldoznacza, że ​​nie musisz obliczać wszystkich wyników w pojedynczym fragmencie pamięci. Zakłada się, że wstępne obliczenie masek poza główną pętlą jest opłacalną optymalizacją.

Jeśli szukasz szybkiej odpowiedzi, właśnie wyszukałem w google „Python power set” i wymyśliłem to: Python Power Set Generator

Oto kopia i wklejanie z kodu na tej stronie:

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

Można tego użyć w następujący sposób:

 l = [1, 2, 3, 4]
 r = [x for x in powerset(l)]

Teraz r to lista wszystkich potrzebnych elementów, którą można posortować i wydrukować:

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(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])

Istnieje udoskonalenie zestawu uprawnień:

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 (przejdź bezpośrednio do Simplification)

Wiem, że wcześniej dodałem odpowiedź, ale bardzo podoba mi się moja nowa implementacja. Biorę zestaw jako dane wejściowe, ale w rzeczywistości może to być dowolny iterowalny zestaw, a ja zwracam zestaw zestawów, który jest zestawem mocy wejścia. Podoba mi się to podejście, ponieważ jest bardziej zgodne z matematyczną definicją zbioru potęg ( zbiór wszystkich podzbiorów ).

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

Jeśli chcesz dokładnie uzyskać wyniki, które zamieściłeś w swojej odpowiedzi, użyj tego:

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

Wyjaśnienie

Wiadomo, że liczba elementów zestawu mocy jest 2 ** len(A)taka, że ​​w forpętli można było wyraźnie zobaczyć .

Muszę przekonwertować dane wejściowe (najlepiej zestaw) na listę, ponieważ przez zestaw jest to struktura danych unikalnych nieuporządkowanych elementów, a kolejność będzie kluczowa do wygenerowania podzbiorów.

selectorjest kluczem do tego algorytmu. Zwróć uwagę, że selectorma taką samą długość jak zestaw wejściowy i aby było to możliwe, używa łańcucha f z dopełnieniem. Zasadniczo pozwala mi to wybrać elementy, które zostaną dodane do każdego podzbioru podczas każdej iteracji. Powiedzmy, że zestaw wejściowy ma 3 elementy {0, 1, 2}, więc selector przyjmie wartości od 0 do 7 (włącznie), które w systemie binarnym to:

000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7

Tak więc każdy bit może służyć jako wskaźnik, czy należy dodać element oryginalnego zestawu, czy nie. Spójrz na liczby binarne i pomyśl o każdej liczbie jako o elemencie super zestawu, co 1oznacza, że jnależy dodać element pod indeksem , a 0to oznacza, że ​​ten element nie powinien być dodawany.

Używam rozumienia zestawu do generowania podzbioru w każdej iteracji i konwertuję ten podzbiór na zestaw, frozensetaby móc go dodać do ps(zestaw potęgowy). W przeciwnym razie nie będę mógł go dodać, ponieważ zestaw w Pythonie składa się tylko z niezmiennych obiektów.

Uproszczenie

Możesz uprościć kod, używając niektórych wyrażeń w Pythonie, dzięki czemu możesz pozbyć się pętli for. Możesz również użyć, zipaby uniknąć używania jindeksu, a kod zakończy się następująco:

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

Otóż ​​to. W tym algorytmie podoba mi się to, że jest jaśniejszy i bardziej intuicyjny niż inne, ponieważ wygląda całkiem magicznie, itertoolsmimo że działa zgodnie z oczekiwaniami.

Uważam, że następujący algorytm jest bardzo przejrzysty i prosty:

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

Innym sposobem generowania zestawu mocy jest generowanie wszystkich liczb binarnych, które mają nbity. Jako potęgę ustawiono ilość liczb z ncyframi 2 ^ n. Zasada tego algorytmu polega na tym, że element może być obecny lub nie w podzbiorze, ponieważ cyfra binarna może mieć wartość jeden lub zero, ale nie obie.

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

Znalazłem oba algorytmy, kiedy brałem MITx: 6.00.2x Wprowadzenie do myślenia obliczeniowego i nauki o danych, i uważam, że jest to jeden z najłatwiejszych do zrozumienia algorytmów, jakie widziałem.

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

Na przykład:

get_power_set([1,2,3])

wydajność

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Chciałem tylko zapewnić najbardziej zrozumiałe rozwiązanie, wersję anty-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

Wyniki

Wszystkie zestawy o długości 0

[()]

Wszystkie zestawy o długości 1

[('x',), ('y',), ('z',)]

Wszystkie zestawy o długości 2

[('x', 'y'), ('x', 'z'), ('y', 'z')]

Wszystkie zestawy o długości 3

[('x', 'y', 'z')]

Aby uzyskać więcej informacji, zobacz dokumentację itertools , a także wpis Wikipedii dotyczący zestawów mocy

Można to zrobić bardzo naturalnie za pomocą 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}

Tylko szybkie odświeżenie zestawu mocy!

Zbiór potęgowy zbioru X to po prostu zbiór wszystkich podzbiorów X, w tym zbiór pusty

Zestaw przykładów X = (a, b, c)

Zestaw mocy = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, {}}

Oto inny sposób na znalezienie zestawu mocy:

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

pełny kredyt dla źródła

Prostym sposobem byłoby wykorzystanie wewnętrznej reprezentacji liczb całkowitych w ramach arytmetyki dopełnienia do 2.

Binarna reprezentacja liczb całkowitych to {000, 001, 010, 011, 100, 101, 110, 111} dla liczb z przedziału od 0 do 7. Dla wartości licznika w postaci liczby całkowitej, biorąc pod uwagę 1 jako włączenie odpowiedniego elementu do zbioru i „0” jako wykluczenie możemy wygenerować podzbiory na podstawie sekwencji zliczania. Liczby należy generować od 0do, pow(2,n) -1gdzie n jest długością tablicy, tj. Liczbą bitów w reprezentacji binarnej.

Bazującą na niej prostą funkcję generatora podzbiorów można zapisać w następujący sposób. Zasadniczo polega

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

a następnie może być używany jako

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

Testowanie

Dodanie następującego w pliku lokalnym

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

daje następujący wynik

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

Z pustym zestawem, który jest częścią wszystkich podzbiorów, możesz użyć:

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

Prawie wszystkie te odpowiedzi używają listraczej niż set, co wydawało mi się trochę oszustwem. Tak więc z ciekawości spróbowałem zrobić naprawdę prostą wersjęset i podsumować ją dla innych ludzi „nowych w Pythonie”.

Zauważyłem, że jest kilka dziwactw związanych z implementacją zestawu w Pythonie . Głównym zaskoczeniem dla mnie była obsługa pustych zestawów. Jest to w przeciwieństwie do implementacji Set Rubiego , w której mogę po prostu zrobić Set[Set[]]i uzyskać Setpusty element zawierający Set, więc początkowo wydawało mi się to trochę zagmatwane.

Aby przejrzeć, robiąc powersetz sets, napotkałem dwa problemy:

1. set()przyjmuje iterowalne, więc set(set())zwróci, set() ponieważ pusty zestaw iterowalny jest pusty (chyba :))
2. aby uzyskać zestaw zestawów set({set()})i set.add(set)nie zadziała, ponieważ set() nie można go hashować

Aby rozwiązać oba problemy, wykorzystałem frozenset(), co oznacza, że ​​nie do końca dostaję to, czego chcę (typ jest dosłownie set), ale korzystam z ogólnego setinterfejsu.

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

Poniżej otrzymujemy 2² (16) frozensets poprawnie jako wyjście:

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

Ponieważ w Pythonie nie ma sposobu, aby mieć s setof setsw, jeśli chcesz zamienić je frozensetna sets, będziesz musiał odwzorować je z powrotem na a list( list(map(set, powerset(set([1,2,3,4])))) ) lub zmodyfikować powyższe.

Być może pytanie się starzeje, ale mam nadzieję, że mój kod komuś pomoże.

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

Użyj funkcji powerset()z pakietu more_itertools.

Udostępnia wszystkie możliwe podzbiory elementu iterowalnego

>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Jeśli chcesz zestawy, użyj:

list(map(set, powerset(iterable)))

Pobieranie wszystkich podzbiorów z rekurencją. Szalona jedna linijka

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

Oparty na rozwiązaniu Haskell

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs

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

Możesz to zrobić w ten sposób:

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

Wynik:

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

Wiem, że to za późno

Istnieje już wiele innych rozwiązań, ale nadal ...

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

Jest to szalone, ponieważ żadna z tych odpowiedzi nie zapewnia zwrotu rzeczywistego zestawu Pythona. Oto niechlujna implementacja, która zapewni zestaw mocy, który w rzeczywistości jest Pythonem 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([]) ])

Chciałbym jednak zobaczyć lepszą implementację.

Oto moja szybka implementacja wykorzystująca kombinacje, ale używająca tylko wbudowanych.

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

Wszystkie podzbiory w zakresie n jako zestaw:

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

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)

Odmianą tego pytania jest ćwiczenie, które widzę w książce „Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming. Edycja 2015”. W tym ćwiczeniu 10.2.11 dane wejściowe są po prostu liczbą całkowitą, a wyjściem powinny być zestawy mocy. Oto moje rozwiązanie rekurencyjne (nie używające niczego innego oprócz podstawowego Pythona3)

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

A wynik jest

[[], [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]] Liczba podlisty: 16

Nie spotkałem tej more_itertools.powersetfunkcji i poleciłbym jej użycie. Nie polecam również używania domyślnej kolejności wyjścia z itertools.combinations, często zamiast tego chcesz zminimalizować odległość między pozycjami i posortować podzbiory elementów z mniejszą odległością między nimi nad / przed elementami z większą odległością między nimi.

Strona z itertoolsprzepisami pokazuje, że używachain.from_iterable

• Zwróć uwagę, że rtutaj pasuje do standardowej notacji dla dolnej części współczynnika dwumianowego , sjest zwykle określany tak, jak nw tekstach matematycznych i kalkulatorach („n Wybierz 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))

Inne przykłady tutaj podają potęgę of [1,2,3,4]w taki sposób, że dwie krotki są wymienione w porządku leksykograficznym (kiedy wypisujemy liczby jako liczby całkowite). Jeśli napiszę odległość między liczbami obok niej (tj. Różnicę), to pokazuje mój punkt widzenia:

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

Prawidłowa kolejność podzbiorów powinna być taka, która jako pierwsza „wyczerpuje” minimalną odległość, na przykład:

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

Używanie tutaj liczb sprawia, że ​​ta kolejność wygląda ["a","b","c","d"]`` źle '', ale rozważ na przykład litery, które są bardziej zrozumiałe, dlaczego może to być przydatne do uzyskania zestawu uprawnień w tej kolejności:

ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3

Efekt ten jest bardziej wyraźny w przypadku większej liczby elementów i dla moich celów stanowi różnicę między zdolnością do opisania zakresów indeksów zestawu potęgi.

(Na kodach Graya jest dużo napisanych itp. Odnośnie kolejności wyjściowej algorytmów w kombinatoryce, nie uważam tego za problem uboczny).

Właściwie właśnie napisałem dość zaangażowany program, który używał tego szybkiego kodu partycji całkowitoliczbowej do wyświetlania wartości we właściwej kolejności, ale potem odkryłem more_itertools.powerseti dla większości zastosowań prawdopodobnie dobrze jest po prostu użyć tej funkcji w następujący sposób:

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)

Pisałem trochę bardziej zaangażować się kod, który będzie drukować PowerSet ładnie (patrz repo na dość funkcje drukowania nie Zamieściliśmy tutaj: print_partitions, print_partitions_by_length, i pprint_tuple).

• Repo: konkretnie uporządkowany zestaw mocypset_partitions.py

To wszystko jest dość proste, ale nadal może być przydatne, jeśli potrzebujesz kodu, który pozwoli ci uzyskać bezpośredni dostęp do różnych poziomów zestawu mocy:

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# /programming/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

Jako przykład napisałem program demonstracyjny CLI, który przyjmuje ciąg znaków jako argument wiersza poleceń:

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

Jeśli chcesz mieć określoną długość podzbiorów, możesz to zrobić w ten sposób:

from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])

Bardziej ogólnie, dla podzbiorów o dowolnej długości można modyfikować arugowanie zakresu. Wynik jest

[(), (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 )]

Oto moje rozwiązania, jest podobne (koncepcyjnie) do rozwiązania lmiguelvargasf.

Pozwólcie, że powiem, że - [przedmiot matematyczny] z definicji powerset zawiera pusty zestaw - [osobisty gust], a także, że nie lubię używać frozensetu.

Tak więc wejście jest listą, a wyjście - listą list. Funkcja mogłaby się zamknąć wcześniej, ale podoba mi się, że element potęgi jest uporządkowany leksykograficznie , czyli zasadniczo ładnie.

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

def powerset(some_set):
    res = [(a,b) for a in some_set for b in some_set]
    return res