20
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Neil Mar 6 '16 at 23:40
  • \$\begingroup\$ @Neil Yes. Otherwise the permutation can be represented as odd number of swaps. \$\endgroup\$ – jimmy23013 Mar 7 '16 at 0:43
  • \$\begingroup\$ Ah yes that's a much better way of putting it. \$\endgroup\$ – Neil Mar 7 '16 at 0:56
  • 1
    \$\begingroup\$ related \$\endgroup\$ – Liam Mar 7 '16 at 3:56
4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Why is the complexity O(n^3)? \$\endgroup\$ – CalculatorFeline Mar 7 '16 at 15:26
  • \$\begingroup\$ @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 \$\endgroup\$ – Ton Hospel Mar 7 '16 at 15:43
  • \$\begingroup\$ Oh. Makes sense. \$\endgroup\$ – CalculatorFeline Mar 7 '16 at 16:37
2
\$\begingroup\$

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@#
]&
\$\endgroup\$
  • \$\begingroup\$ By what magic does this work? \$\endgroup\$ – CalculatorFeline Mar 7 '16 at 5:37
  • 1
    \$\begingroup\$ @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.) \$\endgroup\$ – Neil Mar 7 '16 at 9:25
0
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ I would imagine this takes exponential time. \$\endgroup\$ – feersum Mar 7 '16 at 3:02
  • \$\begingroup\$ Oh, right. I'll have to fix that. \$\endgroup\$ – AtnNn Mar 8 '16 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.