Permutationen eine eindeutige Nummer geben.
Verfasst: Freitag 5. November 2004, 16:42
Guten Tag,
Ich hab vor einiger Zeit in einem Forum für Mathematik angefragt,wie ich einer bestimmten Permutation eine eindeutige Nummer zuweisen kann, ohne alle Permutationen zuvor ausrechen zu müssen. Mir wurde als Antwort folgender Programmablauf gepostet. Da ich aber leider wenig von Mathe verstehe habe ich das Ding nie wirklich verstanden. Ich weiss auch nicht, welche Sprache es ist, vermutlich Code für Mathematica oder Mapple. Ich würde mich deshalb freuen, wenn mir ein Mathematik erfahrener Mensch helfen könnte das Programm in Python zu übersetzen bzw. mir erklärt was die einzellen Teile bedeuten. Unten findet sich im Anhang eine Erklärung was es tut aber fragt mich nicht nach der Bedeutung habe es wie gesagt nie verstanden *heul*
Hier das Programm:
a=0;
for i=1 to n do // Alle Zeichen durchgehen
begin
a=a+f[p]*(n-i)!; // Alle Möglichkeiten für die Restzeichen addieren
for j=f[p]+1 to n do // Und alle nachfolgenden Prioritäten um eins verringern
begin
f[p[j]]=f[p[j]]-1;
end;
end;
a=a+1; // Wenn du es möchtest, dass die Zählung bei 1 und nicht bei 0 beginnt
Ich hoffe jemand kann mir helfen. Wäre wirklich klasse. Ich hänge an diesen Post noch meine Frage und die komplette Antwort aus dem Matheforum an... vielleicht hilft das ja noch beim verstehen des Quelltextes oben.
Wünsche viel Spass und tausend Dank an alle.
Gruß
Informatics
Hier der gesamte Post aus dem Matheforum:
Frage:
Hallo alle zusammen,
Wenn z.B die Buchstaben A B C in allen Möglichkeiten permutiert werden (Im Fall von A B C wären die Möglichkeiten
A B C • A C B • B A C • B C A • C A B • C B A). Ist es dann möglich ohne alle Permutationen auszurechnen, zu bstimmen wie z.B die dritte Permutation lautet oder anders gesagt, kann ich bestimmen das BAC eindeutig, die dritte Permutation ist? Muss ich dafür in einer bestimmten Art permutieren ? Bin für alle Tipps und Hinweise dankbar.
Viele Grüße
Informatics
Hier die ganze Antwort:
Wenn du eine Priorität deiner benutzten Ziffern festlegt kannst du es schon berechnen, in deinem Fall also lexikalisch.
Ich betrachte jetzt mal einfacherhalbe nur Fälle, wo jedes Zeichen einmal auftritt, so dass die Gesamtzahl der Permutationen n! ist, sonst wird es schwieriger. Seien nun also z1,z2,...,zn deine Zeichen aus Z~.
Weiterhin sei f(Z~)-->N eine Funktion, die jederm Zeichen eine Priorität zuordnet (0 niedrigste, n-1 nöchste). (Beispiel: A-->0 ; B-->1; C-->2)
sei eine Zifferfolge p=zk1zk2 ... zkn gegeben mit je: ki<>kj für alle i<>j (also: Jede Ziffer kommt nur einmal vor.)
Dann ist p die a-te Permutation von allen n! Permutationen, wenn man sie lexikalisch (z1<z2<...<zn) anordnet mit folgender Berechnungsvorschrift von a:
Pseudocode: (bin zu faul dadraus eine Formel zu machen! )
Eingaben:
- die Zeichenfolge p als Feld
- die Prioritätenfunktion f als Feld --> f[p] <-- gibt die priorität des i.ten Zeichens an (geordnet von 0 bis n)
a=0;
for i=1 to n do // Alle Zeichen durchgehen
begin
a=a+f[p]*(n-i)!; // Alle Möglichkeiten für die Restzeichen addieren
for j=f[p]+1 to n do // Und alle nachfolgenden Prioritäten um eins verringern
begin
f[p[j]]=f[p[j]]-1;
end;
end;
a=a+1; // Wenn du es möchtest, dass die Zählung bei 1 und nicht bei 0 beginnt
Ich hab vor einiger Zeit in einem Forum für Mathematik angefragt,wie ich einer bestimmten Permutation eine eindeutige Nummer zuweisen kann, ohne alle Permutationen zuvor ausrechen zu müssen. Mir wurde als Antwort folgender Programmablauf gepostet. Da ich aber leider wenig von Mathe verstehe habe ich das Ding nie wirklich verstanden. Ich weiss auch nicht, welche Sprache es ist, vermutlich Code für Mathematica oder Mapple. Ich würde mich deshalb freuen, wenn mir ein Mathematik erfahrener Mensch helfen könnte das Programm in Python zu übersetzen bzw. mir erklärt was die einzellen Teile bedeuten. Unten findet sich im Anhang eine Erklärung was es tut aber fragt mich nicht nach der Bedeutung habe es wie gesagt nie verstanden *heul*
Hier das Programm:
a=0;
for i=1 to n do // Alle Zeichen durchgehen
begin
a=a+f[p]*(n-i)!; // Alle Möglichkeiten für die Restzeichen addieren
for j=f[p]+1 to n do // Und alle nachfolgenden Prioritäten um eins verringern
begin
f[p[j]]=f[p[j]]-1;
end;
end;
a=a+1; // Wenn du es möchtest, dass die Zählung bei 1 und nicht bei 0 beginnt
Ich hoffe jemand kann mir helfen. Wäre wirklich klasse. Ich hänge an diesen Post noch meine Frage und die komplette Antwort aus dem Matheforum an... vielleicht hilft das ja noch beim verstehen des Quelltextes oben.
Wünsche viel Spass und tausend Dank an alle.
Gruß
Informatics
Hier der gesamte Post aus dem Matheforum:
Frage:
Hallo alle zusammen,
Wenn z.B die Buchstaben A B C in allen Möglichkeiten permutiert werden (Im Fall von A B C wären die Möglichkeiten
A B C • A C B • B A C • B C A • C A B • C B A). Ist es dann möglich ohne alle Permutationen auszurechnen, zu bstimmen wie z.B die dritte Permutation lautet oder anders gesagt, kann ich bestimmen das BAC eindeutig, die dritte Permutation ist? Muss ich dafür in einer bestimmten Art permutieren ? Bin für alle Tipps und Hinweise dankbar.
Viele Grüße
Informatics
Hier die ganze Antwort:
Wenn du eine Priorität deiner benutzten Ziffern festlegt kannst du es schon berechnen, in deinem Fall also lexikalisch.
Ich betrachte jetzt mal einfacherhalbe nur Fälle, wo jedes Zeichen einmal auftritt, so dass die Gesamtzahl der Permutationen n! ist, sonst wird es schwieriger. Seien nun also z1,z2,...,zn deine Zeichen aus Z~.
Weiterhin sei f(Z~)-->N eine Funktion, die jederm Zeichen eine Priorität zuordnet (0 niedrigste, n-1 nöchste). (Beispiel: A-->0 ; B-->1; C-->2)
sei eine Zifferfolge p=zk1zk2 ... zkn gegeben mit je: ki<>kj für alle i<>j (also: Jede Ziffer kommt nur einmal vor.)
Dann ist p die a-te Permutation von allen n! Permutationen, wenn man sie lexikalisch (z1<z2<...<zn) anordnet mit folgender Berechnungsvorschrift von a:
Pseudocode: (bin zu faul dadraus eine Formel zu machen! )
Eingaben:
- die Zeichenfolge p als Feld
- die Prioritätenfunktion f als Feld --> f[p] <-- gibt die priorität des i.ten Zeichens an (geordnet von 0 bis n)
a=0;
for i=1 to n do // Alle Zeichen durchgehen
begin
a=a+f[p]*(n-i)!; // Alle Möglichkeiten für die Restzeichen addieren
for j=f[p]+1 to n do // Und alle nachfolgenden Prioritäten um eins verringern
begin
f[p[j]]=f[p[j]]-1;
end;
end;
a=a+1; // Wenn du es möchtest, dass die Zählung bei 1 und nicht bei 0 beginnt