Permutation Quadratwurzel

21

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 3hat 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
Lirtosiast
quelle
Wäre es richtig zu sagen, dass eine Permutation eine Quadratwurzel hat, wenn sie n Zyklen der Länge m enthält, dann ist entweder n gerade oder m ungerade?
Neil
@ Neil Ja. Andernfalls kann die Permutation als ungerade Anzahl von Swaps dargestellt werden.
Jimmy23013
Ah ja, das ist ein viel besserer Ausdruck.
Neil
1
Related
Liam

Antworten:

4

Perl, 124 122 Bytes

Beinhaltet +3 für -alp

Führen Sie mit der 1-basierten Permutation auf STDIN aus:

rootperm.pl <<< "8 3 9 1 5 4 10 13 2 12 6 11 7"

rootperm.pl:

map{//;@{$G[-1]^$_|$0{$_}}{0,@G}=(@G=map{($n+=$s{$_=$F[$_-1]}++)?():$_}(0+$',0+$_)x@F)x2,%s=$n=0for@F}@F;$_="@0{1..@F}"

Komplexität ist O (n ^ 3)

Tonne Hospel
quelle
Warum ist die Komplexität O (n ^ 3)?
CalculatorFeline
@CatsAreFluffy Weil es ein dummes Programm ist :-). Es betrachtet jedes Elementpaar (auch wenn es bereits behandelt wurde, O (n ^ 2)) und zippt seine Zyklen zusammen (ohne zu wissen, wann zu stoppen ist, O (n)) und prüft dann, ob dies ein geeigneter Zyklus für eine Quadratwurzel wäre . In dem Programm können Sie die drei verschachtelten Schleifen als 2 Karten sehen und für
Ton Hospel
Oh. Macht Sinn.
CalculatorFeline
2

Mathematica, 165 167 Bytes

Eine unbenannte Funktion.

PermutationList[Cycles@Join[Riffle@@@#~(s=Select)~EvenQ@*(l=Length)~SortBy~l~Partition~2,#[[Mod[(#+1)/2Range@#,#,1]&@l@#]]&/@#~s~OddQ@*l]&@@PermutationCycles@#,l@#]&

Semi-ungolfed:

PermutationList[
    Cycles@Join[
        Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
        #[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
    ]& @@ PermutationCycles @ #,
    Max@#
]&
Feersum
quelle
Mit welcher Magie funktioniert das?
CalculatorFeline
1
@CatsAreFluffy Wenn ich den semi-ungolfed Code richtig verstanden habe, teilt er die Permutation in Zyklen auf, gruppiert sie nach Länge und erhöht sie für die ungeraden auf die Potenz (Länge + 1) / 2, für die geraden auf die geraden paart sie und zerreißt sie zusammen. (Wenn die geraden Zyklen nicht gepaart werden können, hat die Partition keine Quadratwurzel.)
Neil
0

Prolog - 69 Zeichen

p([],_,[]). p([H|T],B,[I|U]):-p(T,B,U),nth1(H,B,I). f(X,Y):-p(Y,Y,X).

Erläuterung:

permutate([], _, []).                 % An empty permutation is empty
permutate([X|Xs], List, [Y|Ys]) :-    % To permutate List
  permutate(Xs, List, Ys),            % Apply the rest of the permutation
  nth1(X, List, Y).                   % Y is the Xth element of List

root(Permutation, Root) :-            % The root of Permutation
  permutate(Root, Root, Permutation). % Applied to itself, is Permutation
AtnNn
quelle
3
Ich würde mir vorstellen, dass dies exponentielle Zeit in Anspruch nimmt.
Feersum
Oh, richtig. Ich werde das reparieren müssen.
AtnNn