0
$\begingroup$

A permutation of $n$ is a one-to-one and onto function $p$ from $\{0,1,2,\dots,n-1\}$ to itself, such that $p(i) = p(j)$ if and only if $i=j$. The identity permutation is given by $p(i) = i$ for $0 \leq i < n$.

How to check whether $P$ can be written as some power of permutation $Q$ (i.e find $j$ such that $P=Q^j$, $P$ and $Q$ are permutation and given in problem)?

$\endgroup$
2
  • $\begingroup$ Is $Q$ given or only $P$? $\endgroup$ – mathcounterexamples.net Sep 1 '20 at 13:51
  • $\begingroup$ It would help if you gave more context. Are you trying to write a program to solve this efficiently? $\endgroup$ – abhi01nat Sep 1 '20 at 14:06
1
$\begingroup$

As the order of $Q$ is finite, let say equal to $m$ (i.e. $Q^m = Id$), compute $Q^i$ for $1 \le i \le m$ and verify at each step if $Q^i = P$. If yes, you win! If not, the problem has no solution.

Faster solution

Decompose $P,Q$ in cycles. Compute $Q^i$ and verify at each step if the cycle decomposition of $P,Q^i$ are the same.

$\endgroup$
3
  • 2
    $\begingroup$ It might be faster when $m$ is large to break $P$ and $Q$ into their cycle decompositions, check the compatibility of the cycles lengths and elements, and try this algorithm on the cycles separately, starting from the smallest cycle. $\endgroup$ – abhi01nat Sep 1 '20 at 14:04
  • $\begingroup$ @abhi01nat That is true. But as the OP was only asking the question on existence... Also take care that having different cycles decomposition, doesn't imply that the problem is impossible. For example $(1 \ 2 \ 3 \ 4)^2 = (1 \ 3) (2 \ 4)$. $\endgroup$ – mathcounterexamples.net Sep 1 '20 at 14:06
  • $\begingroup$ @Sbc See updated answer. If you want to study algorithm efficiency, asking the question in software engineering stachexchange may be useful. $\endgroup$ – mathcounterexamples.net Sep 1 '20 at 14:21