Mengenpartitionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:02 Sa 10.05.2008 | | Autor: | cofriga |
| Aufgabe | berechnung aller mengenpartitionen
beispiel:
für (1234): (1234),(123)(4),(124)(3),(134)(2),(234)(1),(12)(34),(1)(2)(34),(1)(3)(24),
(1)(4)(23),....,(3)(4)(12),(1)(2)(3)(4) |
hallo ich suche einen algorithmus, um wie in der aufgabe beschrieben, alle partitionen zu finden.
Wenn ich zu einer Menge einen Array gleicher Länge erzeuge, und dann binär durchzähle, was einer Partition entspricht, klappt es nicht ganz:
0000=(1234)
0001=(123)(4)
0010=(12)(3)(4)
0011=(12)(34)
0100=(1)(2)(34)
0101=(1)(2)(3)(4)
0110=(1)(23)(4)
0111=(1)(234)
soweit so gut. jedoch fehlen einige Partitionen:
(1)(3)(24) zb
würde ich weiter zählen, kämen zu viele Lösungen:
1000=(1)(234)=0111
ich habe versucht, in gewissen fällen dieses binäre zählen mit k-teilmengen zu verknüpfen, jedoch kämen da auch zu viele lösungen heraus.
gibt es irgendwelche tipps?
vielen dank im voraus!
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.c-plusplus.de/forum/viewtopic-var-t-is-212791.html
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:26 Sa 10.05.2008 | | Autor: | koepper |
Hallo,
alle Mengenpartitionen einer Menge A bekommst du am einfachsten rekursiv. Sei $a [mm] \in [/mm] A$ und $B := A [mm] \setminus \{a\}$.
[/mm]
Betrachte alle Mengenpartitionen von B. Zu jeder Mengenpartition MPB von B bekommst du Mengenpartitionen von A, indem du nacheinander zu jeder Teilmenge in MPB das Element a hinzufügst und außerdem das Element a einmal als separate Teilmenge hinzufügst.
Die Programmierung erfolgt auf genau diese Weise rekursiv.
LG
Will
|
|
|
|
