프로그래밍/알고리즘

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

riroan 2022. 3. 3. 21:56

백준에 순열 사이클 분할(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번: 순열 사이클

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3

www.acmicpc.net

위 문제의 첫번째 예시는 $(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. 치환군

치환 집합 $A$가 있을 때 일대일 함수 $\sigma : A \rightarrow A$를 $A$의 치환(Permutation)이라고 한다. 쉽게 말해 정의역 원소의 순서가 있다고 가정할 때 그 순서를 바꾸는 함수를 치환이라고 하는 것이

riroan.tistory.com

https://riroan.tistory.com/30

 

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

치환 $\sigma = \begin{pmatrix} 1&2&3&4&5&6&7&8 \\ 3&8&6&7&4&1&5&2 \end{pmatrix}$가 있다고 하자. 이 치환을 반복하다보면 유한번(최대 치환 크기)안에 처음 원소 순서로 돌아온다. $\sigma = \begin..

riroan.tistory.com

 

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

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

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

 

 

# 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