Partition einer Menge (Potenzmenge)

Question

Aufgabe:

Eine Menge mit n Elementen in X Teilmengen aufteilen (alle möglichen Teilmengen auflisten)

Beispiel M = {1,2,3,4,5} (n=5) und X = 3

Herangehensweise:

Potenzmenge bilden

Allen Teilmengen das Kompliment "verknüpfen"

Aus allen Teilmengen und Komplimenten nochmal die Potenzmenge bilden (bis diese die größe 1 (0) haben)

Nur Aufteilungen wählen, die genau X Teilmengen haben.

Frage:

Was wäre ein effizienter Algorithmus?

Was ist die Laufzeit der (Power-Set) Partition? (O(n) = 2 ^ 2 ^ n?)

Answer 1

|P(M)| = 2^5= 32, ohne Mengenklammern geschrieben:

O, 1,2,3,4,5 12, 12,... 123..... 1234, .... 12345 , O = leere Menge

Triple ohne Mengenklammern:

Es gibt (5über3) = 10 Triple:

123, 124,125, 234, 235, 345, 134,145, 135,245

2^(2^5)= 2^32 = ca. 4,3 Milliarden, viel Arbeit zu Fuß

Mehr kann ich dazu leider nicht sagen.

Comments

Ich suche aber nach einer Partition in X(=3) Teilmengen.

Also {1,2} {3,4} {5} oder {1,5} {2,4} {3} wären mögliche Lösungen.

Ich vermute, dass die Laufzeit mit einem smarten Algorithmus auch auf 2^n haltbar ist. Diesen Algorithmus suche ich, zumindest semantisch angedeutet/beschrieben.

---

Sorry, ich habe es anders/falsch verstanden.

Im Nachhinein ist es mir nun klar.

Dann gibt es (5über2) = 10 TM, die Zahl bleibt gleich, weil (5über3) = (5über2).

12,13,14,15,23,24,25,34,35,45

Die Komplimentmenge hat dann die Mächtigkeit: 2^5 -10 = 22.

Die Potenzmenge aus alle TMn und Komplimenten hat sie Mächtigkeit.

2^32 (s.o.)

Zum Partitionsproblem:

https://de.wikipedia.org/wiki/Partitionsproblem

Answer 2

Du möchtest - wenn ich dich richtig verstehe, die Menge {1,2,3,4,5} auf jede mögliche Art in drei Teilmengen aufteilen. Da gibt es einmal die 10 Möglichkeiten der Aufteilung in zwei Mengen zu je einem Element sowie eine Menge mit drei Elementen. Zum anderen kann man auch aufteilen in zwei Mengen zu je zwei Elementen sowie eine Menge mit einem Element.

Comments

Selbstverständlich suche ich nach einem Lösungsweg und der Laufzeit für beliebige n und X. Zumindest eine Formel mit Potenz und Topologie. Die Menge mit 5 Elementen war nur ein Beispiel.

---

Dann hättest du besser geschrieben:

Gesucht ist eine Formel für die Aufgabe: Zerlege eine Menge mit n Elementen auf jede mögliche Art in x Teilmengen und zähle die Anzahl der Möglichkeiten in Abhängigkeit von n und x.

---

Wenn es nur um die Anzahl der Partitionen geht, die wird doch durch die Striling-Zahlen geliefert. Ich verstehe den FS so, dass ein Algorithmus gesucht wird, der alle diese Partitionen liefert??

---

Ok, ich versuche die Frage mit einer besseren Fragestellung zu reposten. (Ich bin selbst kein Mathematiker und definiere deshalb etwas praktischer aus der Informatik)