In der Mathematik ist eine Permutation σ der Ordnung n eine bijektive Funktion von den ganzen Zahlen 1 ... n zu sich selbst. Diese Liste:
2 1 4 3
stellt die Permutation σ , so dass σ (1) = 2, σ (2) = 1, σ (3) = 4 ist , und σ (4) = 3 ist .
Eine Quadratwurzel einer Permutation σ ist eine Permutation, die, wenn sie auf sich selbst angewendet wird, σ ergibt . Zum Beispiel 2 1 4 3
hat die Quadratwurzel τ = 3 4 2 1
.
k 1 2 3 4
τ(k) 3 4 2 1
τ(τ(k)) 2 1 4 3
weil τ ( τ (k)) = σ (k) für alle 1 ≤ k ≤ n.
Eingang
Eine Liste von n > 0 ganzen Zahlen zwischen 1 und n einschließlich, die eine Permutation darstellen. Die Permutation hat immer eine Quadratwurzel.
Sie können stattdessen eine Liste von 0 ... n-1 verwenden, solange Ihre Eingabe und Ausgabe konsistent sind.
Ausgabe
Die Quadratwurzel der Permutation, auch als Array.
Beschränkungen
Ihr Algorithmus muss in der Polynomzeit in n ausgeführt werden . Das heißt, Sie können nicht einfach alle n durchlaufen ! Permutationen der Ordnung n .
Alle eingebauten sind erlaubt.
Testfälle:
Beachten Sie, dass viele Eingänge mehrere mögliche Ausgänge haben.
2 1 4 3
3 4 2 1
1
1
3 1 2
2 3 1
8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6
13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1
quelle
Antworten:
Perl,
124122 BytesBeinhaltet +3 für
-alp
Führen Sie mit der 1-basierten Permutation auf STDIN aus:
rootperm.pl
:Komplexität ist O (n ^ 3)
quelle
Mathematica, 165
167BytesEine unbenannte Funktion.
Semi-ungolfed:
quelle
Prolog - 69 Zeichen
Erläuterung:
quelle