Alle Partitionen einer Menge

Hallo,

ich suche einen Algorithmus, der mir alle Partitionen einer
Menge zurückgibt, Signatur i.e.

List<List<Object>> getPartitionsFor(List<Object>){
.....
}

Als Bonus wäre es super, wenn ich noch nen Parameter maxBlockSize angeben
könnte, so, dass nur Paritionen zurückgeliefert werden, für die gilt,
dass kein Block darin mehr als maxBlockSize Elemente hat.

Ein Pointer zur Lösung würde schon reichen, Partition und Block findet
in Google vor allem Infos zu NTFS usw

Danke und Gruss,
Stefan

asmodis

Dass werden aber schnell ziemlich viele. Menge mit 22 Elementen hat mehr als 1000 moeglich partitionen die sich nur in der Blockgroesse unterscheiden. Dann kommen noch die Permutationen der Elemente hinzu (zwar nicht alle, aber doch viele). Brauchst du wirklich alle Partitionen?

Bashar

algorithmiker_sucher schrieb:

Hallo,

ich suche einen Algorithmus, der mir alle Partitionen einer
Menge zurückgibt, Signatur i.e.

List<List<Object>> getPartitionsFor(List<Object>){
.....
}

Die Signatur ist ungeeignet. Eine Partition ist eine Menge von Mengen, alle Partitionen sind folglich eine Menge von Mengen von Mengen, was sich als List<List<List<Object>>> in der Implementierung niederschlägt (sofern man die wirklich alle explizit berechnen will, aber das scheint ja dein Ziel zu sein).

Als Bonus wäre es super, wenn ich noch nen Parameter maxBlockSize angeben
könnte, so, dass nur Paritionen zurückgeliefert werden, für die gilt,
dass kein Block darin mehr als maxBlockSize Elemente hat.

Block? Komische Sprechweise, kein Wunder, dass du bei Google nichts findest.

Meine Idee ist rekursiv. Basisfall: Eine Menge mit einem Element hat genau eine Partition: $\{a\} \mapsto \{\{\{a\}\}\}$ (die Notation ist verbesserungswürdig). Die leere Menge ist denke ich ein Sonderfall, sie hat keine Partitionen.
Jetzt eine Menge A mit mehr als 1 Element. Sei a irgendein Element von A, und sei B = A \ {a}. Dann bestimmst du alle Partitionen von B. Aus jeder Partition P von B kannst du folgendermaßen Partitionen von A herstellen:

$\{\{a\}\} \cup P$
Für jedes Element M von P: $P \setminus \{M\} \cup \{\{a\} \cup M\}$
Andere Partitionen von A gibt es IMO nicht, und die so konstruierten Partitionen sind auch alle verschieden. Auf bestimmte "Blockgrößen" kannst du an geeigneter Stelle filtern.

asmodis

Hab jetzt mal nachgeschaut. Es gibt zu einer Menge mit 20 Elementen genau
51724158235372 Partitionen. Da kriegt man Platzprobleme wenn man den Rueckgabewert speichern will. Wenn's nur um den Algo geht, dann muesste imho der von Bashar funktionieren.

Bashar

Edit: Erledigt.