Maple Partitionen von Mengen < Maple < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:45 Do 02.09.2004 | | Autor: | Lupine |
Hallo,
ich muss in Maple folgendes programmieren:
"Erzeugen aller Partitionen mit vorgegebener Blockanzahl".
Zwecks Befehlen etc. ist mir alles klar, nur fehlt mir der richtige Ansatz. Soll keine bloßes "Erkennen und Raussuchen" der richtigen Anzahl bestimmter Partitionen nach gewünschter Definition (Bsp: alle Partionen mit zwei Blöcken) sein sondern ein kombinatorischer Ansatz.
Wäre sehr dankbar für Eure Hilfe,
Lupine
P.S.: Ich habe diese Frage in keinem weiteren Forum gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:39 Sa 11.09.2004 | | Autor: | Marc |
Hallo Lupine,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> ich muss in Maple folgendes programmieren:
>
> "Erzeugen aller Partitionen mit vorgegebener
> Blockanzahl".
>
> Zwecks Befehlen etc. ist mir alles klar, nur fehlt mir der
> richtige Ansatz. Soll keine bloßes "Erkennen und
> Raussuchen" der richtigen Anzahl bestimmter Partitionen
> nach gewünschter Definition (Bsp: alle Partionen mit zwei
> Blöcken) sein sondern ein kombinatorischer Ansatz.
Ist mit Partitionierrung hier z.B. die Verteilung der Elemente einer n-elementigen Menge auf k Teilmengen gemeint?
Also z.B. so was hier: Alle möglichen Partitionierungen der Menge {1,2,3}:
{1,2,3}
{1},{2,3}
{1,2},{3}
{1,3},{2} <-- Ist das auch eine Partitionierung (die Reihenfolge der Elemente kann ja nicht mehr eingehalten werden.)
{1},{2},{3}
Sowas würde ich mir zutrauen, in einer Art Pseudo-Code darzustellen, den du dann in Maple übersetzen kannst (ich habe leider kein Maple).
Könntest du bitte noch bestätigen, dass du diese Partitionierungen gemeint hast und ob du noch an einer Antwort interessiert bist?
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:50 Fr 17.09.2004 | | Autor: | Marc |
Hallo Lupine,
ich habe mir noch folgende Gedanken zu der Aufgabe gemacht:
- Eine Partition aus n Elementen läßt sich durch Schnitte einer Zahlenkette herstellen:
Für n=8 hat man die Zahlenkette 12345678.
Schneidet man nun diese Kette auf (veranschaulicht durch |), so erhält man eine Partition: 124|5678
- bei vorgegebener Blockanzahl k ist die Anzahl der "Schnitte" um 1 geringer: Für z.B. 5 Blöcke benötigt man 4 Schnitte.
- damit läßt sich das ganz Problem darstellen als die Verteilung von k-1 Schnitten auf n-1 mögliche Schnittstellen.
Ohne dass es hier von Interesse wäre, kann man also schon feststellen, dass es ${n-1 [mm] \choose [/mm] k-1}$ verschiedene Partitionen mit k Blöcken einer n elementigen Menge gibt.
Im folgenden betrachte ich mal das Beispiel n=8 und k=3 (8 Elemente, 7 Schnittmöglichkeiten, 3 Blöcke, 2 Schnitte)
Programmtechnisch lege ich ein Feld "schnittmuster" der Länge k-1 an, in dem ich die Positionen der Schnitte speichere.
Z.B. bedeutet [1,2] im Beispiel oben die Partition 1|2|345678 und [1,3] die Partition 1|23|45678.
Das Problem ist ja, eine Abzählung der Schnittmuster zu erhalten; man kann aber recht leicht von einem Schnittmuster auf's nächste schliessen, wie du am folgenden Python-Programm sehen kannst. Ich schlage vor, du siehst es dir einmal an, und fragst nach, wenn etwas unklar geblieben sein sollte 
Viele Grüße,
Marc
anzelemente = 8
anzbloecke = 3
anzschnitte = anzbloecke - 1
anzschnittplaetze = anzelemente - 1
# erzeuge Start-schnittmuster: [1,2,3,4,...,anzschnitte]
schnittmuster = range( 1, anzschnitte+1 )
def naechstes_schnittmuster( schnittmuster ):
# finde einen schnitt, der weiter nach rechts gerückt werden kann
gefunden = 0
s = anzschnitte
while s>0 and not gefunden:
# berechne die am weitesten rechts liegende Position
# für diesen Schnitt
maxwert = anzschnittplaetze - anzschnitte + s
if schnittmuster[ s-1 ] < maxwert:
# der aktuelle Wert ist kleiner dem maximalen Wert; also:
gefunden = s
s = s - 1
if gefunden:
# es wurde ein Schnitt gefunden, der nach rechts
# verschoben werden kann
schnittmuster[ gefunden-1 ] += 1
# alle Schnitte rechts davon zurücksetzen
for s in range( anzschnitte-gefunden ):
schnittmuster[ gefunden+s ] = schnittmuster[ gefunden+s-1 ] + 1
else:
schnittmuster = None
return schnittmuster
print schnittmuster
schnittmuster = naechstes_schnittmuster( schnittmuster )
while schnittmuster:
print schnittmuster
schnittmuster = naechstes_schnittmuster( schnittmuster )
|
|
|
|
