Wie bekomme ich alle Teilmengen einer Menge? (Powerset)

92

Gegeben ein Satz

{0, 1, 2, 3}

Wie kann ich die Teilmengen erzeugen:

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

Antworten:

136

Die Python- itertoolsSeite hat genau ein powersetRezept dafür:

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

Ausgabe:

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

Wenn Ihnen dieses leere Tupel am Anfang nicht gefällt, können Sie die rangeAnweisung einfach so ändern range(1, len(s)+1), dass eine Kombination mit 0 Längen vermieden wird.

Mark Rushakoff
quelle
1
Dies ist die schnellste Antwort, die ich finden konnte, wenn ich einige andere Lösungen auf dieser Seite mit dieser unter Verwendung des Python-Timeit-Moduls vergleiche. In bestimmten Fällen kann es jedoch viel schneller sein, ein benutzerdefiniertes Rezept mithilfe von Generatoren zu schreiben und die gewünschte Ausgabe aufzubauen (z. B. zwei Zeichenfolgen zu addieren), wenn Sie die resultierende Ausgabe ändern müssen (z. B. die Buchstaben zu Zeichenfolgen verbinden), z.
Ceasar Bautista
warum wird s = list(iterable)benötigt?
Jack Stevens
@JackStevens, da iterables nicht zurückgespult werden können und nicht __len__implementiert werden müssen; Probieren Sie es powerset((n for n in range(3)))ohne Listenumbruch aus.
hoefling
1
Für große Saiten würde dies viel Speicher verbrauchen!
NoobEditor
1
@AlexandreHuat: Bereiche sind faule Sequenzen, keine Iteratoren. powerset(range(3))würde auch ohnes = list(iterable) gut funktionieren .
user2357112 unterstützt Monica
46

Hier ist mehr Code für ein Powerset. Dies ist von Grund auf neu geschrieben:

>>> 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 Rushakoffs Kommentar gilt hier: "Wenn Ihnen dieses leere Tupel am Anfang nicht gefällt, können Sie die Range-Anweisung einfach in range (1, len (s) +1) ändern, um eine Kombination mit 0 Längen zu vermeiden." ", außer in meinem Fall wechseln Sie for i in range(1 << x)zu for i in range(1, 1 << x).


Wenn ich Jahre später darauf zurückkomme, würde ich es jetzt so schreiben:

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]

Und dann würde der Testcode so aussehen, sagen wir:

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

Verwenden yieldbedeutet, dass Sie nicht alle Ergebnisse in einem einzigen Speicherelement berechnen müssen. Die Vorberechnung der Masken außerhalb der Hauptschleife wird als lohnende Optimierung angesehen.

hughdbrown
quelle
5
Dies ist eine kreative Antwort. Ich habe es jedoch mit timeit gemessen, um es mit Mark Rushakoff zu vergleichen, und festgestellt, dass es deutlich langsamer war. Um den Potenzsatz von 16 Elementen 100 Mal zu erzeugen, waren meine Messungen 0,55 gegenüber 15,6.
Ceasar Bautista
19

Wenn Sie nach einer schnellen Antwort suchen, habe ich gerade bei Google nach "Python Power Set" gesucht und mir Folgendes ausgedacht: Python Power Set Generator

Hier ist ein Copy-Paste aus dem Code auf dieser Seite:

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

Dies kann folgendermaßen verwendet werden:

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

Jetzt ist r eine Liste aller gewünschten Elemente und kann sortiert und gedruckt werden:

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]]
Edan Maor
quelle
1
Im Falle eines leeren Arrays als Eingabe würde der obige Code zurückkehren [[][]], um zu beheben, dass nur die Fälle für die Längenprüfung getrennt werdenif len(seq) == 0: yield [] elif len(seq) == 1: yield seq yield []
Ayush
3
Als Referenz habe ich dies (mit Ayushs Bearbeitung) mit timeit gemessen und es mit dem Powerset-Rezept in Mark Rushakoffs Antwort verglichen. Auf meinem Computer dauerte dieser Algorithmus 1,36 Sekunden, um das Powerset von 16 Elementen 100 Mal zu generieren, während Rushakoffs 0,55 Sekunden dauerte.
Ceasar Bautista
Was wird die zeitliche Komplexität dafür sein?
CodeQuestor
13
def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])
newacct
quelle
8

Es gibt eine Verfeinerung des Powersets:

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
Jingguo Yao
quelle
6

TL; DR (direkt zur Vereinfachung gehen)

Ich weiß, dass ich zuvor eine Antwort hinzugefügt habe, aber meine neue Implementierung gefällt mir sehr gut. Ich nehme einen Satz als Eingabe, aber es könnte tatsächlich jeder iterierbare sein, und ich gebe einen Satz von Sätzen zurück, der der Potenzsatz der Eingabe ist. Ich mag diesen Ansatz, weil er mehr mit der mathematischen Definition der Potenzmenge ( Menge aller Teilmengen ) übereinstimmt .

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

Wenn Sie genau die Ausgabe wünschen, die Sie in Ihrer Antwort gepostet haben, verwenden Sie Folgendes:

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

Erläuterung

Es ist bekannt, dass die Anzahl der Elemente des Leistungssatzes so ist 2 ** len(A), dass dies in der forSchleife deutlich zu sehen ist.

Ich muss die Eingabe (idealerweise eine Menge) in eine Liste konvertieren, da eine Menge eine Datenstruktur aus eindeutigen ungeordneten Elementen enthält und die Reihenfolge für die Generierung der Teilmengen entscheidend ist.

selectorist der Schlüssel in diesem Algorithmus. Beachten Sie, dass selectores die gleiche Länge wie der Eingabesatz hat. Um dies zu ermöglichen, wird ein F-String mit Auffüllung verwendet. Grundsätzlich kann ich so die Elemente auswählen, die während jeder Iteration zu jeder Teilmenge hinzugefügt werden. Angenommen, der Eingabesatz besteht aus 3 Elementen {0, 1, 2}, sodass der Selektor Werte zwischen 0 und 7 (einschließlich) annimmt, die binär sind:

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

Jedes Bit könnte also als Indikator dienen, ob ein Element des ursprünglichen Satzes hinzugefügt werden soll oder nicht. Schauen Sie sich die Binärzahlen an und stellen Sie sich jede Zahl als ein Element der Supermenge vor, was 1bedeutet, dass ein Element am Index jhinzugefügt werden sollte und 0dass dieses Element nicht hinzugefügt werden sollte.

Ich verwende ein Mengenverständnis, um bei jeder Iteration eine Teilmenge zu generieren, und konvertiere diese Teilmenge in eine, frozensetdamit ich sie hinzufügen kann ps(Potenzmenge). Andernfalls kann ich es nicht hinzufügen, da ein Satz in Python nur aus unveränderlichen Objekten besteht.

Vereinfachung

Sie können den Code mithilfe einiger Python-Verständnisse vereinfachen, um diese für Schleifen zu entfernen. Sie können auch verwenden zip, um die Verwendung von jIndex zu vermeiden. Der Code lautet dann wie folgt:

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

Das ist es. Was ich an diesem Algorithmus mag, ist, dass er klarer und intuitiver ist als andere, weil es ziemlich magisch aussieht, sich darauf zu verlassen itertools, obwohl er wie erwartet funktioniert.

lmiguelvargasf
quelle
5
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

Beispielsweise:

get_power_set([1,2,3])

Ausbeute

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
jmkg
quelle
1
Das Ändern einer Schleifenvariablen ( power_set) in der von ihr gesteuerten Schleife ist eine sehr fragwürdige Praxis. Angenommen, Sie haben dies anstelle des vorgeschlagenen variablenmodifizierenden Codes geschrieben : power_set += [list(sub_set)+[elem]]. Dann endet die Schleife nicht.
Hughdbrown
5

Ich habe den folgenden Algorithmus sehr klar und einfach gefunden:

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

Eine andere Möglichkeit, das Powerset zu generieren, besteht darin, alle Binärzahlen mit nBits zu generieren . Als nPotenzsatz ist die Anzahl der Ziffern 2 ^ n. Das Prinzip dieses Algorithmus ist, dass ein Element in einer Teilmenge vorhanden sein kann oder nicht, da eine Binärziffer eins oder null sein kann, aber nicht beide.

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

Ich habe beide Algorithmen gefunden, als ich MITx: 6.00.2x Einführung in Computational Thinking und Data Science genommen habe, und ich halte es für einen der am einfachsten zu verstehenden Algorithmen, die ich je gesehen habe.

lmiguelvargasf
quelle
3

Ich wollte nur die verständlichste Lösung anbieten, die Anti-Code-Golf-Version.

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

Die Ergebnisse

Alle Sätze der Länge 0

[()]

Alle Sätze der Länge 1

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

Alle Sätze der Länge 2

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

Alle Sätze der Länge 3

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

Weitere Informationen finden Sie in den itertools-Dokumenten sowie im Wikipedia-Eintrag zu Power Sets

Gourneau
quelle
2

Nur eine schnelle Auffrischung des Netzes!

Die Potenzmenge einer Menge X ist einfach die Menge aller Teilmengen von X einschließlich der leeren Menge

Beispielmenge X = (a, b, c)

Power Set = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, {}}

Hier ist eine andere Möglichkeit, die eingestellte Leistung zu finden:

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

volle Gutschrift zur Quelle

grepit
quelle
2

Mit einer leeren Menge, die Teil aller Teilmengen ist, können Sie Folgendes verwenden:

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

Ein einfacher Weg wäre, die interne Darstellung von ganzen Zahlen unter der Komplementarithmetik von 2 zu nutzen.

Die binäre Darstellung von ganzen Zahlen ist {000, 001, 010, 011, 100, 101, 110, 111} für Zahlen im Bereich von 0 bis 7. Bei einem ganzzahligen Zählerwert wird 1 als Einbeziehung des entsprechenden Elements in die Sammlung und '0' betrachtet. Als Ausschluss können wir Teilmengen basierend auf der Zählsequenz generieren. Zahlen müssen von bis erzeugt werden 0, pow(2,n) -1wobei n die Länge des Arrays ist, dh die Anzahl der Bits in binärer Darstellung.

Eine darauf basierende einfache Teilmengengeneratorfunktion kann wie folgt geschrieben werden. Es beruht im Grunde

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

und dann kann es als verwendet werden

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

Testen

Hinzufügen von Folgendem in lokaler Datei

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

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

gibt folgende Ausgabe

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']]
ViFI
quelle
Dies mag in Bezug auf Wartbarkeit oder Lesbarkeit nicht praktikabel sein, aber es hat mich umgehauen. Vielen Dank für das Teilen, intelligente Lösung!
Lorey
1

Fast alle diese Antworten verwenden listeher als set, was sich für mich wie ein Betrug anfühlte. Aus Neugier habe ich versucht, eine einfache Version wirklich zu machenset und für andere "Python-Neulinge" zusammenzufassen.

Ich fand, dass es ein paar Kuriositäten im Umgang mit Pythons Set-Implementierung gibt . Die Hauptüberraschung für mich war der Umgang mit leeren Sets. Dies steht im Gegensatz zu Rubys Set-Implementierung , bei der ich einfach Set[Set[]]eine Setenthaltende leer machen kannSet , sodass ich sie anfangs etwas verwirrend fand.

Zur Überprüfung, dabei powersetmit sets, begegnete ich zwei Probleme:

  1. set()nimmt eine iterable, set(set())wird also zurückkehren, set() weil die leere Menge iterable leer ist (duh ich denke :))
  2. eine Reihe von Sets zu bekommen, set({set()})und set.add(set)wird nicht funktionieren, weil set() nicht hashbar ist

Um beide Probleme zu lösen, habe ich davon Gebrauch gemacht frozenset(), was bedeutet, dass ich nicht ganz das bekomme, was ich will (Typ ist wörtlich set), sondern das gesamte setInterace benutze.

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

Unten erhalten wir 2² (16) frozensets korrekt als Ausgabe:

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

Da es keine Möglichkeit gibt , eine haben , setvon sets in Python, wenn Sie diese aktivieren möchten frozensets in sets, werden Sie sie in eine zur Karte zurück haben list( list(map(set, powerset(set([1,2,3,4])))) ) oder die oben zu ändern.

Alex Moore-Niemi
quelle
1

Vielleicht wird die Frage alt, aber ich hoffe, mein Code hilft jemandem.

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
Lisandro Di Meo
quelle
ew, Rekursion! =)
-Kohomologie
Wahrscheinlich nicht der effizienteste Weg, aber es ist immer interessant, den rekursiven Weg zu sehen!
Lisandro Di Meo
1

Verwenden Sie die Funktion powerset()aus dem Paket more_itertools.

Ergibt alle möglichen Teilmengen der Iterable

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

Wenn Sie Sets möchten, verwenden Sie:

list(map(set, powerset(iterable)))
Alexandre Huat
quelle
1
So viele Leute erfinden das Rad hier neu, IMHO ist dies die beste Antwort, da es möglicherweise bereits in Ihren Abhängigkeiten liegt, da es von vielen gängigen Bibliotheken, z. B. Pytest, benötigt wird. libraries.io/pypi/more-itertools/dependents
lorey
1

Abrufen aller Teilmengen mit Rekursion. Verrückter Einzeiler

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

Basierend auf einer Haskell-Lösung

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs
Paweł Rubin
quelle
NameError: name 'List' is not defined
4LegsDrivenCat
@ 4LegsDrivenCat Ich habe ListImport hinzugefügt
Paweł Rubin
1
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
Mohamed_Abdelmadjid Boudis
quelle
Nur-Code-Antworten gelten als minderwertig: Stellen Sie sicher, dass Sie erklären, was Ihr Code tut und wie er das Problem löst. Es wird sowohl dem Fragesteller als auch zukünftigen Lesern helfen, wenn Sie Ihrem Beitrag weitere Informationen hinzufügen können. Siehe Erklären vollständig
codebasierter
0

Dies ist wild, da keine dieser Antworten tatsächlich die Rückgabe eines tatsächlichen Python-Sets liefert. Hier ist eine chaotische Implementierung, die ein Powerset liefert, das tatsächlich ein Python ist 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([]) ])

Ich würde jedoch gerne eine bessere Implementierung sehen.

Matthew Turner
quelle
Guter Punkt, aber das OP möchte eine Liste von Mengen als Ausgabe, damit Sie (in Python 3) tun können [*map(set, chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))]; Die Funktion arg von mapkann sein, frozensetwenn Sie es vorziehen.
PM 2Ring
0

Hier ist meine schnelle Implementierung, bei der Kombinationen verwendet werden, aber nur integrierte Funktionen verwendet werden.

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
Daniel
quelle
0

Alle Teilmengen im Bereich n wie eingestellt:

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 "{}")
Cestmoimahdi
quelle
0
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)
Subbhashit Mukherjee
quelle
0

Eine Variation der Frage ist eine Übung, die ich im Buch "Discovering Computer Science: Interdisziplinäre Probleme, Prinzipien und Python-Programmierung. Ausgabe 2015" sehe. In dieser Übung 10.2.11 ist die Eingabe nur eine Ganzzahl, und die Ausgabe sollte die Potenzsätze sein. Hier ist meine rekursive Lösung (ich verwende nichts anderes als 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))

Und die Ausgabe ist

[[], [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]] Anzahl von Unterlisten: 16

GeorgiosDoumas
quelle
0

Ich war nicht auf die more_itertools.powersetFunktion gestoßen und würde empfehlen, sie zu verwenden. Ich empfehle außerdem, nicht die Standardreihenfolge der Ausgabe von zu verwenden itertools.combinations. Oft möchten Sie stattdessen den Abstand minimieren zwischen den Positionen und die Teilmengen von Elementen mit kürzerem Abstand über / vor den Elementen mit größerem Abstand zwischen ihnen sortieren.

Die itertoolsRezeptseite zeigt die Verwendungchain.from_iterable

  • Beachten Sie, dass das rhier mit der Standardnotation für den unteren Teil eines Binomialkoeffizienten übereinstimmt , das sist in der Regel bezeichnet als nin der Mathematik Texten und auf Rechner ( „n Wählen Sie 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))

Die anderen Beispiele hier geben das Powerset von [1,2,3,4]so an, dass die 2-Tupel in "lexikografischer" Reihenfolge aufgelistet sind (wenn wir die Zahlen als ganze Zahlen drucken). Wenn ich den Abstand zwischen den Zahlen daneben schreibe (dh den Unterschied), zeigt dies meinen Punkt:

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

Die richtige Reihenfolge für Teilmengen sollte die Reihenfolge sein, in der der minimale Abstand zuerst "erschöpft" wird, wie folgt:

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

Wenn Sie hier Zahlen verwenden, sieht diese Reihenfolge "falsch" aus. Beachten Sie jedoch beispielsweise die Buchstaben ["a","b","c","d"] Es ist klarer, warum dies nützlich sein kann, um das Powerset in dieser Reihenfolge zu erhalten:

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

Dieser Effekt ist bei mehr Elementen stärker ausgeprägt und macht für meine Zwecke den Unterschied zwischen der Möglichkeit, die Bereiche der Indizes des Powersets sinnvoll zu beschreiben.

(Es ist viel geschrieben Für die Ausgabereihenfolge von Algorithmen in der Kombinatorik Gray-Codes usw. , ich sehe dies nicht als Nebenproblem).

Ich habe gerade ein ziemlich kompliziertes Programm geschrieben, das diesen schnellen ganzzahligen Partitionscode verwendet hat, um die Werte in der richtigen Reihenfolge auszugeben, aber dann habe ich festgestellt, dass es more_itertools.powersetfür die meisten Anwendungen wahrscheinlich in Ordnung ist, diese Funktion einfach so zu verwenden:

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)

Ich schrieb etwas mehr beteiligt Code, der sehr schön die Powerset gedruckt wird (siehe die repo für ziemlich Funktionen Drucken ich hier nicht enthalten habe: print_partitions, print_partitions_by_length, und pprint_tuple).

Dies ist alles ziemlich einfach, kann aber dennoch nützlich sein, wenn Sie Code benötigen, mit dem Sie direkt auf die verschiedenen Ebenen des Powersets zugreifen können:

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

Als Beispiel habe ich ein CLI-Demoprogramm geschrieben, das eine Zeichenfolge als Befehlszeilenargument verwendet:

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
Louis Maddox
quelle
0

Wenn Sie eine bestimmte Länge von Teilmengen wünschen, können Sie dies folgendermaßen tun:

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

Allgemeiner können Sie für Teilmengen mit beliebiger Länge das Bereichsarugment ändern. Die Ausgabe ist

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

Adel
quelle
0

Sie können es so machen:

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

Ausgabe:

[[], [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]]
Blake
quelle
Könnte ich vorschlagen, dass Sie beim Posten einer Codelösung so freundlich sind, eine detaillierte Erklärung zu geben, was der Code tut und warum Sie diese oder jene Methode verwenden, um ein Problem zu lösen. Neue Codierer sollten sich nicht nur einen Codeblock ansehen und ihn kopieren / einfügen, ohne genau zu wissen, was der Code tut und warum. Danke und willkommen bei Stackoverflow.
Yokai vor
-1

In Python 3.5 oder höher können Sie die yield fromAnweisung zusammen mit itertools.combinations verwenden :

def subsets(iterable):
    for n in range(len(iterable)):
        yield from combinations(iterable, n + 1)
Juan C. Roldán
quelle