55. Permutation Cycle Decomposition

순열(Permutation)은 $1$ 이상 $n$ 이하의 정수가 한 번씩 등장하는 특수한 형태의 수열이다. $n$은 순열의 길이이며 $0$보다 큰 정수이다. 이 글에 나오는 순열과는 비슷하지만 약간 다르다.

특정한 조건을 만족하는 순열의 개수를 다음과 같은 공식으로 구할 수 있다.

• 길이가 $n$인 순열의 개수는 $n!$이다.
• 길이가 $n$인 순열 $a: \{a_1, a_2, \ldots a_n\}$ 중 $a_i=i$를 만족하는 $i$가 존재하지 않는 순열의 개수를 $f(n)$이라고 하면, $f(1)=0, f(2)=1$이고, $n \ge 3$인 경우 $f(n)=(n-1)(f(n-2)+f(n-1))$이다. 또한 그런 $i$가 $k$개 존재하는 순열의 개수는 $_n\mathrm{C}_k \times f(n-k)$이다. $(0 \le k < n)$ $i = n$인 수열의 개수는 $1$이다.

---

순열 $a: \{a_1, a_2, \ldots a_n\}$에서 $f^1(x)=f(x)=a_x, f^k(x)=f(f^{k-1}(x))$로 정의하면, $f(x)$는 일대일 대응이며, 수열 $\{f^0(x), f^1(x), f^2(x), \ldots \}$은 주기 $p$를 갖는다. 이 수열을 주기 단위로 끊은 수열 $\{f^0(x), f^1(x), f^2(x), \ldots f^{p-1}(x) \}$를 순열 사이클(Permutation Cycle)이라고 하고 $p$를 사이클의 길이라고 한다. 하나의 순열에는 한 개 이상의 순열 사이클이 존재하며, 순열을 각각의 순열 사이클로 분할하는 것을 순열 사이클 분할(Permutation Cycle Decomposition)이라고 한다.

 

순열 $a: \{a_1, a_2, \ldots a_n\}$에 대해 $F^1(a)=F(a):\{f(a_1), f(a_2), \ldots f(a_n)\}, F^k(a):F(F^{k-1}(a))$로 정의하면 $F^0(a)=\{1, 2, \ldots n\}$이고, 순열 수열 $\{F^1(a), F^2(a), \ldots \}$은 주기 $t$를 갖는다. 이때 $t$는 순열 $a$에 존재하는 각각의 순열 사이클의 길이의 최소공배수와 같다.

 

순열이 주어지면 다음과 같은 코드로 사이클의 개수, 주기 등을 구할 수 있다. 함수의 실행이 끝나면 $s$에는 사이클의 개수가, $p$에는 순열 수열의 주기가 저장된다.

int p = 1, s = 0;
void f(int n)
{
    for(int i = 1; i <= n; i++)
    {
        if(!vi[i])
        {
            int k = 0;
            for(int x = i; !vi[x]; x = a[x])
            {
                vi[x] = 1;
                k++;
            }
            p = p / __gcd(p, k) * k;
            s++;
        }
    }
}

 

예시 코드에는 없지만, 필요한 경우 순열 사이클을 직접 뽑아낼 수도 있다.

 

[연습문제]

 

BOJ 10451. 순열 사이클 (Silver II)

순열 사이클의 개수를 세는 문제이다.

 

BOJ 2487. 섞기 수열 (Gold III)

순열 수열의 주기를 구하는 문제이다.

 

BOJ 20692. Permutation Transformation (Platinum III)

순열 수열의 주기를 구해야 하는데, 순열 수열이 $\{F^{2^0}(a), F^{2^1}(a), F^{2^2}(a), \ldots \}$의 형태로 되어 있다. 일단 순열 사이클의 주기를 각각 구해야 하는데, 이것들의 최소공배수가 너무 커질 수 있기 때문에 소인수의 개수를 각각 저장한다. 다음으로 각각의 홀수 소인수의 거듭제곱에 대한 $2$의 위수를 모두 곱하고 소인수 $2$의 개수를 더하면 답이 나온다. 위수에 대한 내용은 이 글에서 설명했다.

 

BOJ 2569. 짐정리 (Platinum I)

각각의 값을 크기에 따라 번호를 매기면 이것은 순열이 되고, 이 순열을 사이클로 분할한다. 전체 원소 중 가장 작은 값을 $v$, 사이클에서 가장 작은 값을 $w$, 사이클의 길이를 $p$, 사이클의 원소들의 합을 $s$라고 하면 이 사이클을 정렬하는 데 드는 최소 비용은 $s+\min((p-2)w, w+(p+1)v)$이다. 각각의 비용을 다 더하면 답이 나온다.

 

CF 1327D. Infinite Path (2200)

각각의 순열 사이클을 확인하면서 답을 구한다. 사이클의 길이가 $p$일 때 $p$의 약수를 하나씩 확인하면서 $F^k(a)$가 Infinite Path를 포함하는 최소의 $k$를 찾고, 찾은 값들 중에서 다시 최솟값을 찾으면 답이 나온다.

 

→ solved.ac tag: permutation_cycle_decomposition