21
1
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 – 2016-03-06T23:40:29.917
@Neil Yes. Otherwise the permutation can be represented as odd number of swaps. – jimmy23013 – 2016-03-07T00:43:09.770
Ah yes that's a much better way of putting it. – Neil – 2016-03-07T00:56:27.587
1related – Liam – 2016-03-07T03:56:10.583