Kata

Overview

Given a permutation (a list representing an arrangement of $[0,1,\mathrm{.}\mathrm{.}\mathrm{.},n-1][0,\; 1,\; ...,\; n\; -\; 1]$ for some $nn$), find a square root of that permutation (a new arrangement that, when applied to itself, gives the original permutation.)

Explanation

In this kata, a permutation of length $nn$ is a list containing each non-negative integer less than $nn$ exactly once, in some order. For instance, $[1,7,6,3,2,4,5,0][1,\; 7,\; 6,\; 3,\; 2,\; 4,\; 5,\; 0]$ is a permutation of length $88$. ¹

Each permutation can be thought of as a rearrangement of the list $[0,1,\mathrm{.}\mathrm{.}\mathrm{.},n-1][0,\; 1,\; ...,\; n\; -\; 1]$. It may also be thought of as a function, where the the inputs are the indices and the outputs are the values at those indices:

k      0     1     2     3     4     5     6     7
f(k)   1     7     6     3     2     4     5     0

Like any function, $f(k)f(k)$ may be composed with another function, or with itself. The function $f(f(k))f(f(k))$ will also represent a permutation of the same length:

k        0     1     2     3     4     5     6     7
f(k)     1     7     6     3     2     4     5     0
f(f(k))  7     0     5     3     6     2     4     1

We may call $[7,0,5,3,6,2,4,1][7,\; 0,\; 5,\; 3,\; 6,\; 2,\; 4,\; 1]$ the square of $[1,7,6,3,2,4,5,0][1,\; 7,\; 6,\; 3,\; 2,\; 4,\; 5,\; 0]$. It makes sense, then, to call $[1,7,6,3,2,4,5,0][1,\; 7,\; 6,\; 3,\; 2,\; 4,\; 5,\; 0]$ a square root of $[7,0,5,3,6,2,4,1][7,\; 0,\; 5,\; 3,\; 6,\; 2,\; 4,\; 1]$.

Like real numbers, permutations may have multiple square roots, or no square roots. The only other square root of $[7,0,5,3,6,2,4,1][7,\; 0,\; 5,\; 3,\; 6,\; 2,\; 4,\; 1]$ is $[1,7,4,3,5,6,2,0][1,\; 7,\; 4,\; 3,\; 5,\; 6,\; 2,\; 0]$, though some permutations may have many more square roots. On the other hand, the permutation $[1,0][1,\; 0]$ has none. (To see this, note that the only permutations of length $22$ are $[0,1][0,\; 1]$ and $[1,0][1,\; 0]$, both of which square to $[0,1][0,\; 1]$.)

Objective

Write a function get_square_root that accepts a permutation as a list of integers for its input. If that permutation has one or more square roots as defined above, return any one of those permutations also in list form. Otherwise, return None.

Example 1

has_square_root([7, 0, 5, 3, 6, 2, 4, 1])
# should return [1, 7, 6, 3, 2, 4, 5, 0] or [1, 7, 4, 3, 5, 6, 2, 0]

Example 2

has_square_root([1, 0])
# should return None

All inputs will be lists of length $nn$, where $1\le n\le 50001\; \backslash leq\; n\; \backslash leq\; 5000$. Inputs will always be valid permutations, containing exclusively non-negative integers less than $nn$, and never containing duplicates.

---

1. It is more standard in mathematics for permutations be rearrangements of $[1,2,\mathrm{.}\mathrm{.}\mathrm{.},n][1,\; 2,\; ...,\; n]$, but zero-indexed permutations are easier to work with here. The actual objects being arranged do not fundamentally matter. There is a more useful notation for permutations called cycle notation, but this is not used in this kata.