# 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