Permutation Square Root

Question

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

• Neil: 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?
• jimmy23013: @Neil Yes. Otherwise the permutation can be represented as odd number of swaps.
• Neil: Ah yes that's a much better way of putting it.
• Liam: related

Answer 1

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)

• CalculatorFeline: Why is the complexity O(n^3)?
• Ton Hospel: @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
• CalculatorFeline: Oh. Makes sense.

Answer 2

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

• CalculatorFeline: By what magic does this work?
• Neil: @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.)

Answer 3

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

• feersum: I would imagine this takes exponential time.
• Etienne Laurin: Oh, right. I'll have to fix that.