Ich betrachte alle Permutationen von 0, ..., n-1 in lexikographischer Reihenfolge. Ich gebe zwei Ränge, i und j, und fragte nach dem Rang der Permutation, die sich aus der Anwendung der i-ten Permutation auf die j-te Permutation ergibt.
Ein paar Beispiele für n = 3:
p (3) = [1, 2, 0], p (4) = [2, 0, 1], Ergebnis = [0, 1, 2], Rang = 0
Wenn i = j = 4, erhalten wir [2, 0, 1] für sich selbst ist [1, 2, 0], rank = 3.
Was mir bisher eingefallen ist: Ich wandle die Ränge über Lehmer-Codes in ihre jeweiligen Permutationen um, berechne die gewünschte Permutation und wandle über Lehmer-Codes zurück in den Rang.
Kann jemand einen Weg vorschlagen, um den Rang der gewünschten Permutation von den anderen zwei Rängen zu bekommen, ohne die Permutationen tatsächlich berechnen zu müssen? Speichern des n! x n! Array ist keine Option.
-editieren- Beachten Sie, dass ich nicht mit lexikographischer Ordnung verheiratet bin, wenn eine andere Reihenfolge dies ermöglichen würde.
-edit- Hier sind die n! von n! Gitter für n = 3 & amp; 4, für lexikographische Ränge. Zeile I wird in Spalte j indiziert, um die Ausgabe zu erhalten. Beachten Sie, dass das Gitter n = 3 identisch mit der oberen linken Ecke des Gitters n = 4 ist.
%Vor%Hier sind die Fakten für n = 4. Ich habe die letzte Ziffer, die immer Null ist, für Kompaktheit weggelassen.
%Vor%Ich habe einen Algorithmus gefunden, um zwischen Permutationen und Rängen in linearer Zeit zu konvertieren. Das ist nicht ganz das, was ich will, aber es ist wahrscheinlich gut genug. Es stellt sich heraus, dass die Tatsache, dass mir die lexikographische Ordnung egal ist, wichtig ist. Die Rangfolge, die dabei verwendet wird, ist seltsam. Ich werde zwei Funktionen geben, eine, die von einem Rang in eine Permutation konvertiert, und eine, die das Gegenteil tut.
Zuerst, um zu entranken (gehe von Rang zu Permutation)
%Vor%Als nächstes zum Rang:
%Vor%Das ist der Pseudocode. Für mein Projekt werde ich vorsichtig sein, mit einer Kopie von p zu arbeiten, damit ich es nicht mutiere, wenn ich seinen Rang berechne.
Die Laufzeit von beiden ist O (n).
Es gibt ein schönes, lesbares Papier, das erklärt, warum das funktioniert: Ranking & amp; Unranking-Permutationen in linearer Zeit, von Myrvold & amp; Ruskey, Information Processing Letters, Band 79, Ausgabe 6, 30. September 2001, Seiten 281-284.
Wenn Sie zusätzlich zu R nicht mit einem bestimmten P verbunden sind, könnten wir die Permutationsfunktion neu definieren, um eine mögliche Antwort zu ermöglichen. Die Funktion newPerm unten würde eine Liste in Bezug auf R mit der gleichen Konsistenz wie die Permutierungsfunktion, die in "indiziert" wird, permutieren.
Das folgende Beispiel ist nicht auf Effizienz optimiert (z. B. kann Ranging / Unranching in O (n) durchgeführt werden). Die letzten beiden Zeilen der Ausgabe vergleichen die neu definierte Permutierungsfunktion mit der Permutierungsfunktion "Indizierung". Wie Sie sehen, erzeugen beide die gleiche Anzahl von eindeutigen Permutationen, wenn sie der Permutationsmenge zugeordnet werden. Die Funktion f wäre die Antwort auf die Frage.
Haskell-Code:
%Vor%Ausgabe:
%Vor%Tags und Links algorithm language-agnostic math permutation combinatorics