Lexikographische Anordnung von Permutationen

Computer: Software & Programmierung Programmierung allgemein
#1

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

#2

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

#3

Nachtrag

  1. p({})={}

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

Gruss
Enno

#4

Hallo,

ich weiss nicht, ob Du das meinst:

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

MfG,

Master.

#5

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)

#6

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]