Informatik

Potenzmenge und Partitionen berechnen

Potenzmenge berechnen

Definition:  Die Potenzmenge Potenzmenge (M) einer Menge M ist die Menge aller Teilmengen von M:

Potenzmenge (M)  =  { T  |  T ⊆ M }

Die Potenzmenge der leeren Menge ∅ ist die Menge

Potenzmenge (∅)  =  {∅}

Die leere Menge enthält 0 Elemente, die Potenzmenge der leeren Menge enthält 1 Element. Allgemein enthält die Potenzmenge 2n Elemente, wenn die Menge n Elemente enthält, wobei n ∈ ℕ0.

Die folgende Funktion powerset in der Programmiersprache Python berechnet rekursiv die Potenzmenge Potenzmenge (M) der Menge M = {1, ..., n} mit n ∈ ℕ0.

# berechnet die Potenzmenge der Menge M = {1,..,n}
def powerset(n):
    if n==0:
        return [[]]
    else:
        p=powerset(n-1)
        return p+[x+[n] for x in p]

Als Ergebnis liefert beispielsweise der Aufruf powerset(1) die Liste

[[], [1]]

und der Aufruf powerset(2) die Liste

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

Die Ergebnisse veranschaulichen das Vorgehen der Rekursion: An die einzelnen Listen von powerset(1) wird jeweils noch das Element 2 angehängt, und diese neu entstandenen Listen werden zusätzlich an powerset(1) angehängt. Mit jedem Rekursionsschritt verdoppelt sich die Anzahl der Listen, sodass deren Anzahl korrekterweise der Zweierpotenz des jeweiligen Arguments n entspricht.

Partitionen berechnen

Definition:  Eine Partition einer Menge M ist eine Menge P von nichtleeren, paarweise disjunkten Teilmengen von M, deren Vereinigung M ergibt.

P ⊆ Potenzmenge (M)  ist eine Partition, wenn gilt

  •  VereinigungT ∈ P  T  =  M
  • S, T ∈ P,   S ≠ T   ⇒   S ∩ T  =  ∅
  • ∅  ∉  P

Beispiel:  Wenn M = {1, 2, 3} ist, so ist beispielsweise

P  =  { {1, 2}, {3} }

eine Partition der Menge M.

Unterschiedliche Partitionen

Alle Partitionen der Menge M = {1, 2, 3} sind

{ {1, 2, 3} }
{ {1, 3}, {2} }
{ {1, 2}, {3} }
{ {1}, {2, 3} }
{ {1}, {2}, {3} }

Definition:  Die Anzahl der k-elementigen Partitionen einer Menge mit n ∈ ℕ Elementen wird mit Sn,k bezeichnet, dies ist die sogenannte Stirling-Zahl zweiter Art (nach J. Stirlingzur Person).

Die Aufzählung des obigen Beispiels zeigt, dass es für eine Menge mit 3 Elementen eine 1-elementige Partition gibt, drei 2-elementige Partitionen und eine 3-elementige Partition.

Die folgende Tabelle enthält die Stirling-Zahlen zweiter Art Sn,k für Mengen mit n = 1, ..., 6 Elementen. In den Zeilen ist n abgetragen, in den Spalten k. Beispielsweise gilt S5,2 = 15 oder, wie oben gesehen, S3,2 = 3.

In der letzten Spalte, die mit B überschrieben ist, steht jeweils die Summe der Stirling-Zahlen der betreffenden Zeile. Diese Zahlen heißen bellsche Zahlen (nach E.T. Bellzur Person). Die bellsche Zahl Bn gibt die Anzahl aller unterschiedlichen Partitionen einer Menge M mit n Elementen an. So ist beispielsweise B3 = 5, denn es gibt wie oben gesehen 5 unterschiedliche Partitionen einer Menge mit 3 Elementen.

Die bellschen Zahlen erscheinen als Folge A000110 in der Online Encyclopedia of Integer Sequences (OEIS).

 

     123456B
111
2112
31315
4176115
51152510152
61319065151203

 

Partitionen erzeugen

Die Vorgehensweise ist ähnlich wie bei der Berechnung der Potenzmenge, nämlich rekursiv, indem ausgehend von den Partitionen der Menge {1, ..., n-1} die Partitionen der Menge {1, ..., n} berechnet werden. Neue Partitionen der Menge {1, ..., n} entstehen, indem für jede Partition der Menge {1, ..., n-1}

Die folgende Funktion partitions(n) berechnet die Menge aller Partitionen der n-elementigen Menge M = {1, ..., n}.

 

from copy import *
# berechnet alle Partitionen der Menge M = {1,..,n}
def partitions(n):
    if n==1:
        return [[[1]]]
    else:
        ps=partitions(n-1)
        qs=[]
        for p in ps:                 # alle Partitionen durchlaufen
            qs+=[p+[[n]]]            # zu p die Menge {n} hinzufügen
            for i in range(len(p)):  # alle Mengen einer Partition durchlaufen
                q=deepcopy(p)
                q[i]+=[n]            # zu jeder Menge das Element n hinzufügen
                qs+=[q]
    return qs

 

Als Ergebnis liefert beispielsweise der Aufruf partitions(1) die Liste

[[[1]]]

also eine Liste, die nur eine Partition enthält, die nur aus der Liste [1] besteht. Der Aufruf partitions(2) ergibt die Liste

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

mit den zwei Partitionen {{1}, {2}} und {{1, 2}}. Der Aufruf partitions(3) ergibt die Liste

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

bestehend aus 5 Partitionen.

Ausprobieren

Unter powerset-partitions.ipynb steht ein jupyter-Notebook zum Ausprobieren zur Verfügung.

 

[up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 25.01.2021   Updated: 12.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden