Permutationen eine eindeutige Nummer geben.

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
informatics
User
Beiträge: 11
Registriert: Freitag 16. Juli 2004, 09:33

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
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Freitag 5. November 2004, 17:09

Hi!

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

Gruß, mawe
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Freitag 5. November 2004, 17:39

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 :wink:
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Freitag 5. November 2004, 17:49

Hi!
Milan hat geschrieben: @mawe: von dem Code, den du gepostet hast, ist leider die Umkehrfunktion gesucht
informatics hat geschrieben: ... wie z.B die dritte Permutation lautet oder anders gesagt, kann ich bestimmen das BAC eindeutig, die dritte Permutation ist?
Anscheinend ist beides gesucht :D

Code: Alles auswählen

# 3. Permutation
print getPerm(["A","B","C"],2)  # -> ['B', 'A', 'C']
Gruß, mawe
informatics
User
Beiträge: 11
Registriert: Freitag 16. Juli 2004, 09:33

Freitag 5. November 2004, 18:05

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
User
Beiträge: 11
Registriert: Freitag 16. Juli 2004, 09:33

Samstag 6. November 2004, 13:43

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
Antworten