Find $F$ such that $F*F$ =P

Question

Let $P$ is given permutation. How can I calculate $F$ such that $F*F=P$.

Answer 1

This is not always possible, but you can move along the cycle decomposition of $P$. For any odd cycle $(a_1\,a_2\,\ldots\,a_m)$ where $m=2k-1$ is odd, note that $(a_1\,a_2\,\ldots\,a_m)^2=(a_1\,a_3\,\ldots\,a_m\,a_2\,a_4\,\ldots\,a_{m-1})$ is an odd cycle of the same length. Vice versa, we can reverse this and write $$(a_1\,a_2\,\ldots\,a_m)= (a_1\,a_{k+1}\,a_2\,a_{k+2}\,\ldots\,a_k)^2.$$ On the other hand, the square of an even cycle (as above, with $m=2k$), is $(a_1\,a_3\,\ldots \,a_{2k-1})(a_2\,a_4\,\ldots \,a_{2k})$, so to reverse this, you can only pick two equal length even cycles of $P$ and "mix" them to a cycle of length $2m$. This will work out if and only if there is no even number $m$ such that $P$ has an odd number of cycles of lemngth $m$.