Indexing Platz Permutationen in andere Rang Permutationen

ich alle Permutationen von 0 bedenkt, ..., n-1 in lexikographische Ordnung. Ich bin zwei Reihen gegeben, i und j, und bat den Rang der Permutation zu finden, die die i-te Permutation auf die j-te Permutation von der Anwendung führt.Indexing Platz Permutationen in andere Rang Permutationen

ein paar Beispiele für n = 3:

p (3) = [1, 2, 0], p (4) = [2, 0, 1], result = [0, 1, 2 ], rank = 0

Bei i = j = 4, erhalten wir [2, 0, 1], um sich selbst angelegt ist [1, 2, 0], rank = 3.

Was ich bin gekommen, bis jetzt: 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 Rang.

Kann jemand einen Weg vorschlagen, den Rang der gewünschten Permutation von den anderen beiden Reihen zu bekommen, ohne tatsächlich die Permutationen berechnen? Speichern des n! x n! Array ist keine Option.

-edit- Bitte beachte, dass ich nicht zu lexicographic um vermähle wenn eine andere Reihenfolge dies ermöglichen würde.

-edit- Hier sind die n! von n! Gitter für n = 3 & 4, für lexikographische Ränge. Zeile I wird in Spalte j indiziert, um die Ausgabe zu erhalten. Beachten Sie, dass das Raster n = 3 identisch mit der oberen linken Ecke des Rasters n = 4 ist.

00|01|02|03|04|05| 
01|00|03|02|05|04| 
02|04|00|05|01|03| 
03|05|01|04|00|02| 
04|02|05|00|03|01| 
05|03|04|01|02|00| 

00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23| 
01|00|03|02|05|04|07|06|09|08|11|10|13|12|15|14|17|16|19|18|21|20|23|22| 
02|04|00|05|01|03|08|10|06|11|07|09|14|16|12|17|13|15|20|22|18|23|19|21| 
03|05|01|04|00|02|09|11|07|10|06|08|15|17|13|16|12|14|21|23|19|22|18|20| 
04|02|05|00|03|01|10|08|11|06|09|07|16|14|17|12|15|13|22|20|23|18|21|19| 
05|03|04|01|02|00|11|09|10|07|08|06|17|15|16|13|14|12|23|21|22|19|20|18| 
06|07|12|13|18|19|00|01|14|15|20|21|02|03|08|09|22|23|04|05|10|11|16|17| 
07|06|13|12|19|18|01|00|15|14|21|20|03|02|09|08|23|22|05|04|11|10|17|16| 
08|10|14|16|20|22|02|04|12|17|18|23|00|05|06|11|19|21|01|03|07|09|13|15| 
09|11|15|17|21|23|03|05|13|16|19|22|01|04|07|10|18|20|00|02|06|08|12|14| 
10|08|16|14|22|20|04|02|17|12|23|18|05|00|11|06|21|19|03|01|09|07|15|13| 
11|09|17|15|23|21|05|03|16|13|22|19|04|01|10|07|20|18|02|00|08|06|14|12| 
12|18|06|19|07|13|14|20|00|21|01|15|08|22|02|23|03|09|10|16|04|17|05|11| 
13|19|07|18|06|12|15|21|01|20|00|14|09|23|03|22|02|08|11|17|05|16|04|10| 
14|20|08|22|10|16|12|18|02|23|04|17|06|19|00|21|05|11|07|13|01|15|03|09| 
15|21|09|23|11|17|13|19|03|22|05|16|07|18|01|20|04|10|06|12|00|14|02|08| 
16|22|10|20|08|14|17|23|04|18|02|12|11|21|05|19|00|06|09|15|03|13|01|07| 
17|23|11|21|09|15|16|22|05|19|03|13|10|20|04|18|01|07|08|14|02|12|00|06| 
18|12|19|06|13|07|20|14|21|00|15|01|22|08|23|02|09|03|16|10|17|04|11|05| 
19|13|18|07|12|06|21|15|20|01|14|00|23|09|22|03|08|02|17|11|16|05|10|04| 
20|14|22|08|16|10|18|12|23|02|17|04|19|06|21|00|11|05|13|07|15|01|09|03| 
21|15|23|09|17|11|19|13|22|03|16|05|18|07|20|01|10|04|12|06|14|00|08|02| 
22|16|20|10|14|08|23|17|18|04|12|02|21|11|19|05|06|00|15|09|13|03|07|01| 
23|17|21|11|15|09|22|16|19|05|13|03|20|10|18|04|07|01|14|08|12|02|06|00|

Hier sind die Factoradics für n = 4. Ich habe die letzte Ziffer, die immer Null ist, für die Kompaktheit weggelassen.

000|001|010|011|020|021|100|101|110|111|120|121|200|201|210|211|220|221|300|301|310|311|320|321| 
001|000|011|010|021|020|101|100|111|110|121|120|201|200|211|210|221|220|301|300|311|310|321|320| 
010|020|000|021|001|011|110|120|100|121|101|111|210|220|200|221|201|211|310|320|300|321|301|311| 
011|021|001|020|000|010|111|121|101|120|100|110|211|221|201|220|200|210|311|321|301|320|300|310| 
020|010|021|000|011|001|120|110|121|100|111|101|220|210|221|200|211|201|320|310|321|300|311|301| 
021|011|020|001|010|000|121|111|120|101|110|100|221|211|220|201|210|200|321|311|320|301|310|300| 
100|101|200|201|300|301|000|001|210|211|310|311|010|011|110|111|320|321|020|021|120|121|220|221| 
101|100|201|200|301|300|001|000|211|210|311|310|011|010|111|110|321|320|021|020|121|120|221|220| 
110|120|210|220|310|320|010|020|200|221|300|321|000|021|100|121|301|311|001|011|101|111|201|211| 
111|121|211|221|311|321|011|021|201|220|301|320|001|020|101|120|300|310|000|010|100|110|200|210| 
120|110|220|210|320|310|020|010|221|200|321|300|021|000|121|100|311|301|011|001|111|101|211|201| 
121|111|221|211|321|311|021|011|220|201|320|301|020|001|120|101|310|300|010|000|110|100|210|200| 
200|300|100|301|101|201|210|310|000|311|001|211|110|320|010|321|011|111|120|220|020|221|021|121| 
201|301|101|300|100|200|211|311|001|310|000|210|111|321|011|320|010|110|121|221|021|220|020|120| 
210|310|110|320|120|220|200|300|010|321|020|221|100|301|000|311|021|121|101|201|001|211|011|111| 
211|311|111|321|121|221|201|301|011|320|021|220|101|300|001|310|020|120|100|200|000|210|010|110| 
220|320|120|310|110|210|221|321|020|300|010|200|121|311|021|301|000|100|111|211|011|201|001|101| 
221|321|121|311|111|211|220|320|021|301|011|201|120|310|020|300|001|101|110|210|010|200|000|100| 
300|200|301|100|201|101|310|210|311|000|211|001|320|110|321|010|111|011|220|120|221|020|121|021| 
301|201|300|101|200|100|311|211|310|001|210|000|321|111|320|011|110|010|221|121|220|021|120|020| 
310|210|320|110|220|120|300|200|321|010|221|020|301|100|311|000|121|021|201|101|211|001|111|011| 
311|211|321|111|221|121|301|201|320|011|220|021|300|101|310|001|120|020|200|100|210|000|110|010| 
320|220|310|120|210|110|321|221|300|020|200|010|311|121|301|021|100|000|211|111|201|011|101|001| 
321|221|311|121|211|111|320|220|301|021|201|011|310|120|300|020|101|001|210|110|200|010|100|000|

Quelle

2014-09-22 Dave

Wenn Sie nicht zu lexicographic um vermählt werden, wäre dies nicht verwandt sein, mit weniger Umwandlung zwei Werte als 'n' zu einem Wert von weniger als' n' in einer konsistenten Art und Weise? –

@ גגעדבעדבקן Ich denke nicht. Nehmen wir an, wir definieren f (R, n, i, j) als die Funktion, die eine Rangfolge R von Permutationen annimmt (also R ist eine Liste einzigartiger Permutationen), n ist die Länge der Permutationen (Elemente 0 bis n-1; | R | = n!), Und i und j sind die Indizes der beiden Eingangspermutationen in R, dann ist f (R, n, i, j) der Index der Ausgangspermutation in R. Mir ist egal was R ist, aber ich denke nicht, dass es ein triviales Problem ist. Vielleicht interpretiere ich Ihren Kommentar falsch - könnten Sie etwas erläutern oder ein Beispiel geben? – Dave

Sorry, ich habe 'n' für die Anzahl der Permutationen verwechselt. In diesem Fall habe ich zwei Werte kleiner oder gleich zu | R | auf einen Wert kleiner als oder gleich zu | R | in einer konsequenten, nicht-trivialen Art und Weise. –

ich einen Algorithmus zwischen Permutationen und Reihen in linearer Zeit zu konvertieren gefunden. 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.

Erstens, um unrank (von Rang gehen zu Permutation)

Initialize: 
n = length(permutation) 
r = desired rank 
p = identity permutation of n elements [0, 1, ..., n] 

unrank(n, r, p) 
    if n > 0 then 
    swap(p[n-1], p[r mod n]) 
    unrank(n-1, floor(r/n), p) 
    fi 
end

nächster Rang:

Initialize: 
p = input permutation 
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n) 
n = length(p) 

rank(n, p, q) 
    if n=1 then return 0 fi 
    s = p[n-1] 
    swap(p[n-1], p[q[n-1]]) 
    swap(q[s], q[n-1]) 
    return s + n * rank(n-1, p, q) 
end

, dass der Pseudo-Code ist. Für mein Projekt werde ich vorsichtig sein, mit einer Kopie von p zu arbeiten, so dass ich es nicht mutiere, wenn ich seinen Rang berechne.

Die Laufzeit von diesen beiden ist O (n).

Es ist ein schönes, gut lesbares Papier zu erklären, warum das funktioniert: Ranking & Unranking Permutationen in linearer Zeit, von Myrvold & Ruskey, Information Processing Letters Volume 79, Issue 6, die 30. September 2001, Seiten 281-284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Quelle

2014-09-25 00:51:12 Dave

Wenn zusätzlich zu R, Sie sind nicht entweder zu einem bestimmten P fest gebunden, könnten wir die Permutation Funktion neu definieren eine mögliche Antwort zu erleichtern. Die folgende Funktion newPerm würde eine Liste in Bezug auf R mit der gleichen Konsistenz wie die Permutierungsfunktion, die "indiziert".

Das folgende Beispiel ist für die Effizienz nicht optimiert (beispielsweise kann Ranking/unranking 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:

import Data.List (sort,permutations) 
import Data.Maybe (fromJust) 

sortedPermutations = sort $ permutations [0,1,2,3,4,5,6] 

rank p = fromJust (lookup p rs) where rs = zip sortedPermutations [0..] 

unrank r = fromJust (lookup r ps) where ps = zip [0..] sortedPermutations 

tradPerm p s = foldr (\a b -> s!!a : b) [] p 

newPerm p s = unrank (f (rank p) (rank s)) 

f r1 r2 = let l = r1 - r2 in if l < 0 then length sortedPermutations + l else l

Ausgang:

*Main Data.List> unrank 3 
[0,1,2,3,5,6,4] 

*Main Data.List> unrank 8 
[0,1,2,4,5,3,6] 

*Main Data.List> f 3 8 
5035 

*Main Data.List> newPerm [0,1,2,3,5,6,4] [0,1,2,4,5,3,6] 
[6,5,4,3,0,2,1] 

*Main Data.List> rank [6,5,4,3,0,2,1] 
5035 

*Main Data.List> length $ group $ sort $ map (tradPerm [1,2,5,0,4,3,6]) sortedPermutations 
5040 

*Main Data.List> length $ group $ sort $ map (newPerm [1,2,5,0,4,3,6]) sortedPermutations 
5040

Quelle

2014-09-23 23:10:27

Wenn "f 3 8 = 5035" bedeutet, dass die Indexierung in die 8. Permutation mit Elementen der 3. Permutation die 5035. Permutation ergibt und die 3. und 8. Permutation wie in Ihrer Ausgabe beschrieben sind, dann hätten wir "unranked 5035 = [0 1,2,4,3,6,5] Dh, dies scheint nicht die Eigenschaft zu haben, dass der Ausgabe-Rang der Rang der Permutation ist, die Sie erhalten, wenn Sie mit den Elementen der ersten Permutation in die zweite Permutation einsteigen Ich basiere dies nur auf der Ausgabe, die Sie angegeben haben, da ich Haskell nicht kenne. – Dave

@DaveGalvin Vielen Dank für Ihren Kommentar Ich nehme an, dass das, was Sie als "Indizierung in" bezeichnen, "permutieren" bedeutet, das ist Ich benutze die 3. Permutation, um den 8. zu permutieren (ich denke, mein 'i' und' j' sind in meinem Beispiel umgeschaltet, oops). Da ich in diesem Fall "Permutation" neu definiere, bedeutet "unrank (f (Rang p) (Rang s)) ', mein" Indexieren in "oder" Permutieren "geschieht durch die Funktion' newPerm', die '[6,5,4,3,0,2,1 ] '. unrank 5035 ergibt auch "[6,5,4,3,0,2,1]", wie es sollte. Ich habe es nicht gründlich getestet oder getestet, ich habe nur etwas Unkonventionelles versucht, das konsistent sein könnte. –

@DaveGalvin in Bezug auf Haskell - Sie können mehr oder weniger den Code lesen, wie Sie matchen würden. 'rank' und' unrank' suchen einfach den Index oder die Permutation in einer Liste auf, 'tradPerm' ist die Art und Weise, wie Sie traditionell permutieren (durch" indexieren in "). –

Indexing Platz Permutationen in andere Rang Permutationen

Antwort

Verwandte Themen