Permutation Square Root

In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list:

2 1 4 3


represents the permutation σ such that σ(1) = 2, σ(2) = 1, σ(3) = 4, and σ(4) = 3.

A square root of a permutation σ is a permutation that, when applied to itself, gives σ. For example, 2 1 4 3 has the square root τ =3 4 2 1.

k           1 2 3 4
τ(k)        3 4 2 1
τ(τ(k))     2 1 4 3


because τ(τ(k)) = σ(k) for all 1≤k≤n.

Input

A list of n>0 integers, all between 1 and n inclusive, representing a permutation. The permutation will always have a square root.

You may use a list of 0...n-1 instead as long as your input and output are consistent.

Output

The permutation's square root, also as an array.

Restrictions

Your algorithm must run in polynomial time in n. That means you can't just loop through all n! permutations of order n.

Any builtins are permitted.

Test cases:

Note that many inputs have multiple possible outputs.

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

• Would I be correct in saying that for a permutation to have a square root then if it contains n cycles of length m then either n is even or m is odd?
– Neil
Mar 6, 2016 at 23:40
• @Neil Yes. Otherwise the permutation can be represented as odd number of swaps. Mar 7, 2016 at 0:43
• Ah yes that's a much better way of putting it.
– Neil
Mar 7, 2016 at 0:56
• related
– Liam
Mar 7, 2016 at 3:56

Perl, 124 122 bytes

Includes +3 for -alp

Run with the 1 based permutation on STDIN:

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}"


Complexity is O(n^3)

• Why is the complexity O(n^3)? Mar 7, 2016 at 15:26
• @CatsAreFluffy Because it's a stupid program :-). It considers each pair of elements (even if already handled, O(n^2)) and zips their cycles together (not even knowing when to stop, O(n)) then checks if that would be a proper cycle for a square root. In the program you can see the 3 nested loops as 2 maps and a for Mar 7, 2016 at 15:43
• Oh. Makes sense. Mar 7, 2016 at 16:37

Mathematica, 165 167 bytes

An unnamed function.

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@#
]&

• By what magic does this work? Mar 7, 2016 at 5:37
• @CatsAreFluffy if I've understood the semi-ungolfed code correctly, it splits the permutation into cycles, groups them by length, then for the odd ones it raises them to the power (length+1)/2 while for the even ones it pairs them up and riffles them together. (If the even cycles can't be paired then the partition has no square root.)
– Neil
Mar 7, 2016 at 9:25

Prolog - 69 chars

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


Explanation:

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

• I would imagine this takes exponential time. Mar 7, 2016 at 3:02
• Oh, right. I'll have to fix that. Mar 8, 2016 at 3:59