Order of a permutation (Editorial)

Let $p$ be a given permutation, and let $p[i]$ denote the element of the permutation located at position $i$. Consider the sequence of elements: i, p[i], p[p[i]], ... . Since the number of elements in the permutation is finite, there exists a smallest $k$ such that p[i]^k = i. The sequence of elements i, p[i], p[p[i]], ..., p[i]^{k-1}, where p[i]^k = i, is called a cycle. The length of the cycle is $k$.

Any permutation can be represented as a list of cycles. For example, the permutation [4, 3, 2, 5, 1, 6] can be represented as (1, 4, 5)(2, 3)(6).

For example, the sequence (1, p[1], p[p[1]]) = (1, 4, 5) forms a cycle because p[p[p[1]]] = p[1]^3 = 1. The length of this cycle is $3$.

The order of a permutation is the least common multiple (LCM) of the lengths of its cycles.

Example

In the first example, the permutation [4, 3, 2, 5, 1, 6] is represented as (1, 4, 5)(2, 3)(6). The lengths of the cycles are $3,2$ and $1$. The order of the permutation is LCM(3, 2, 1) = 6.

In the second example, the permutation [4, 3, 6, 8, 9, 7, 2, 1, 5] is represented as (1, 4, 8)(2, 3, 6, 7)(5, 9). The lengths of the cycles are $3,4$ and $2$. The order of the permutation is LCM(3, 4, 2) = 12.

Algorithm implementation

The array $p$ stores the input permutation. The array $used$ is used to mark processed elements.

#define MAX 101
int p[MAX], used[MAX];

Read the input permutation.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&p[i]);

The variable $res$ is used to compute the order of the permutation $p$.

res = 1;
memset(used, 0, sizeof(used));

Iterate over the indices of the permutation. For each processed index $i$, set used[i] = 1.

for (i = 1; i <= n; i++)
  if (!used[i])
  {

The cycle with the element $p[i]$ is not found yet. Search for the length of the cycle $len$ in the permutation, starting from index j = i. To do this, consecutively move through the indices j, p[j], p[p[j]], ..., until we encounter an already processed element. All visited indices $j$ are marked as visited by setting used[j] = 1.

    len = 0;
    j = i;
    while (!used[j])
    {
      used[j] = 1;
      j = p[j];
      len++;
    }

The variable $len$ contains the length of the current cycle found. Compute the LCM of the lengths of all cycles.

    res = lcm(res, len);
  }

Print the answer.

printf("%d\n", res);