Permutationen eine eindeutige Nummer geben.

[informatics]

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

[mawe]

Hi!

Ich bin auch keine Leuchte in Mathe, aber für so etwas gibt's ja das Cookbook

Gruß, mawe

[Milan]

Hi, die Erklärung leuchtet mir ein (von wegen Priorität und alle Elemente nur einmal), nicht aber die Umsetzung. Habs mal eben umgesetzt und es liefert für verschiedene Sachen mitunter selbe Werte... kann nicht sein.

Code: Alles auswählen

def num(p,f):
    p=p[:]
    f=f.copy()
    a=0
    n=len(p)
    for i in xrange(1,n):
        a=a+f[p[i]]*reduce(lambda x,y: x*y,xrange(1,n-i),1)
        for j in xrange(f[p[i]]+1,n):
            f[p[j]]=f[p[j]]-1
    a=a+1
    return a

@mawe: von dem Code, den du gepostet hast, ist leider die Umkehrfunktion gesucht

[mawe]

Hi!

@mawe: von dem Code, den du gepostet hast, ist leider die Umkehrfunktion gesucht

... wie z.B die dritte Permutation lautet oder anders gesagt, kann ich bestimmen das BAC eindeutig, die dritte Permutation ist?

Anscheinend ist beides gesucht

Code: Alles auswählen

# 3. Permutation
print getPerm(["A","B","C"],2)  # -> ['B', 'A', 'C']

Gruß, mawe

[informatics]

Hallo,
Danke für die wahnsinnig schnelle Hilfe. Ja ich brauche beides eine Funktion, die mir die Nummer einer Permutation ausgibt und eben eine, die aus dieser Nummer, die dazugehörige Permutation erzeugt. Der Tipp mit der Seite war gut *bookmarksetzentue*. Danke auch für die Umkehrung.. Ist diese deine verbesserte Umsetzung. Du hattest ja angemerkt, dass diese bei verschiedenen Sachen mitunter selbe Werte ausgibt also nicht ganz korrekt zu sein scheint.

Dank und Grüße

Informatics

[informatics]

Hallo,
Noch mal herzlichen Dank für die Hilfe. Ich habe gestern noch versucht die Umkehrung des ganzen, die Milan gepostet hat auszuprobieren. Hab es aber leider nicht geschafft. Welche Werte muss ich beim aufrufen übergeben? p muss die Permutation sein aber was ist f? Eine kleine Erläuterung wäre super. Danke.

Viele Liebe Grüße

Informatics