Zum Inhalt springen
Frage 31. Mai 2003, 13:04 Uhr · 5 Antworten

Lexikographische Anordnung von Permutationen

Hallo!

Ich weiss zwar, das man die Anzahl aller
Permutationen ohne Wiederholung von n Elementen mit
Hilfe der Fakultät berechnen kann, aber,
ich möchte gerne alle Permutationen von n Elementen
berechnen. Wie kann ich das am einfachsten anstellen?
Kennt jemand den Algorithmus dafür?
Ich vermute mal das man einen rekursiven Algorithmus benötigt.

Ich habe schon gegooglet, aber ich finde immer wieder nur
die Definitionen, was eine Fakultät ist etc. aber keinen
Algorithmus zum berechnen aller Möglichkeiten.

Wer kann mir weiterhelfen?

Vielen Dank im Voraus!

Dennis

Diese Frage stammt aus dem Jahr 2003. Weißt du es heute besser?

Aktuelle Antwort ergänzen

5 Antworten

Hallo,
im wesentlichen so:

  1. p({})={}
  2. p({a} + M)={[a] o p(M)} + {[b] o p({a} + M/{b}) | b\in M und ab}

p(X) liefert die Menge aller Permutation über X, wobei eine Permutation als geordnete Menge (Liste) dargestellt wird. + ist die disjunkte Vereinigung, o die Listenkonkatenation (hochgezogen auf Mengen von Listen), / die Mengendifferenz und \in die Elementbeziehung von Mengen.

  1. besagt das sich aus der leeren Menge keine Permutation bilden lassen. 2. erklärt für eine mind. 1-elementige Menge, wie sich die Menge der Permutationen aus einen (beliebig) ausgewählten Element und der verbleibenden Menge bestimmt. Einfach ausgedrückt, vereinigt man die Permutationsmengen bei denen ein ausgewähltes Element der Menge die 1.te Position einnimmt .

Z.B. p({a,b,c})={[a] o p({b,c}),[b] o p({a,c}), [c] o p({b,a})}
= {[a,b] o p({c}), [a,c] o p({b}), [b,a] o p({c}), [b,c] o p({a}), [c,b] o p({a}), [c,a] o p({b})}
… = {[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,b,a],[c,a,b]}

Gruss
Enno

0 Hilfreich
Antwort auf Enno_Sandner_66c4aazum Beitrag ↑

Hallo, im wesentlichen so: p({})={} p({a} + M)={[a] o p(M)} + {[b] o p({a} + M/{b}) | b\in M und ab} p(X) liefert die Menge aller Permutation über X, wobei eine Permutation als geordnete Menge (Liste) dargestellt wird. + …

Nachtrag

  1. p({})={}

p({})={[]} tut’s besser 😉

Gruss
Enno

0 Hilfreich

Hallo,

ich weiss nicht, ob Du das meinst:

fak(n) = if (n==0) then 1 else n*fak(n-1)

MfG,

Master.

0 Hilfreich
Antwort auf Tristan_b00ce9zum Beitrag ↑

Hallo, ich weiss nicht, ob Du das meinst: fak(n) = if (n==0) then 1 else n*fak(n-1) MfG, Master.

Hallo,
er sucht nicht die Anzahl sondern die Darstellung der Permutationen. Z.B. bei drei Elementen A,B,C ist er an den 6 Permutationen ABC,ACB,BAC,BCA,CAB,CBA interessiert, nicht an der Zahl 6.

Gruss
Enno

ich weiss nicht, ob Du das meinst:
fak(n) = if (n==0) then 1 else n*fak(n-1)

0 Hilfreich

Hi,

falls es nur ums Berechnen der Permutationen geht (und weniger um den Algorithmus dazu), gibt es in C++ die Funktionen
next_permutation und prev_permutation.
Diese erzeugen jeweils die naechste/vorherige Permutation in lexikographischer Reihenfolge.

MfG,

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Deine Antwort

Zum Antworten bitte anmelden oder kostenlos registrieren.