[알고리즘] 순열 사이클 분할

백준에 순열 사이클 분할(permutation cycle decomposition)이라는 태그가 있어서 공부를 하게 되었다.

 

기본적인 개념은 다음과 같다.

어떤 순열 $(a_1, a_2, \dots , a_n)$이 있으면 $a_i = f(i)$인 함수가 있다고 생각해보자.

$f^2(i) = f(f(i))$라고 할 때 $i = f^k(i)$인 $1 \le k \le n$을 찾을 수 있다.

그럼 $k$번 연산하는 과정에서 나온 수들을 모으면 $(f(i), f^2(i), \dots, f^k(i))$가 나올 것이고 이것을 하나의 순열 사이클이라고 한다.

순열 사이클 안에 존재하는 원소들은 모두 같은 순열 사이클이 될 것이다.

모든 원소에 대해 수행하면 여러개의 순열 사이클이 나오는데 이를 구하는 것을 순열 사이클 분할이라고 한다.

 

예를 들어보자.

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

위 문제의 첫번째 예시는 $(3,2,7,8,1,4,5,6)$이다.

$i=1$부터 시작하면 $1 \rightarrow 3 \rightarrow 7 \rightarrow 5 \rightarrow 1$이다.

이를 모든 원소에 대해 수행해보자.

$i=2 : 2 \rightarrow 2$ 

$i=3 : 3 \rightarrow 7 \rightarrow 5 \rightarrow 1 \rightarrow 3$

$i=4 : 4 \rightarrow 8 \rightarrow 6 \rightarrow 4$

$i=5 : 5 \rightarrow 1 \rightarrow 3 \rightarrow 7 \rightarrow 5$

$i=6 : 6 \rightarrow 4 \rightarrow 8 \rightarrow 6$

$i=7 : 7 \rightarrow 5 \rightarrow 1 \rightarrow 3 \rightarrow 7$

$i=8 : 8 \rightarrow 6 \rightarrow 4 \rightarrow 8$

중복을 제거하면 순열사이클은 $(1,3,7,5), (2), (4,8,6)$으로 3개가 나오게 된다.

 

이런식으로 순열사이클을 직접구하거나 개수를 세는 문제가 주로 나온다.

 

 

또한 지난번에 포스팅한 현대대수학에 굉장히 유사한 내용이 있다.

https://riroan.tistory.com/24

[현대대수학] 8. 치환군

https://riroan.tistory.com/30

[현대대수학] 9. 궤도, 순환치환, 교대군

 

문제에서 나타내는 순열을 치환으로 보자.

그럼 순열 사이클은 궤도가 된다.

그리고 위 포스트에 "모든 유한집합의 치환들은 여러개의 서로 소인 순환치환들의 곱으로 나타낼 수 있다."라는 성질이 있기 때문에 하나의 순열은 반드시 순열 사이클 분할이 가능하다는게 보장된다.

 

 

# O(N)
# arr의 범위를 0~n-1로 가정
def permutation_cycle_decomposition(arr):
    n = len(arr)
    check = [False] * n
    ans = []
    for i in range(n):
        if not check[i]:
            ix = arr[i]
            tmp = [i]
            check[i] = True
            while ix != i:
                tmp.append(ix)
                check[ix] = True
                ix = arr[ix]
            ans.append(tmp)
    return len(ans), ans