순열의 기우성과 Inversion

코드포스가 뜸해서 앳코더를 시작했다. ARC 136 B를 풀었다.

수열의 연속된 세 개의 값 $a_i, a_{i+1}, a_{i+2}$를 $a_{i+2}, a_i, a_{i+1}$로 바꾸는 shift 연산을 써서 수열 $A$를 $B$로 만들 수 있는지 묻는 문제다.

$O(N^2)$ 시뮬레이션으로 풀었는데, 에디토리얼을 보니 $O(N\log{N})$까지 가능하다. 애드혹인 줄 알았는데 수학에서 중요하게 다루어지는 토픽이란다. 또 나만 모르는 웰노운이다.

호환

호환(transposition)을 정의하자. 치환(permutation) 즉, 순열의 어떤 인덱스 $i$, $j$의 값을 교환하는 연산이다.

호환은 inversion 개수의 홀짝을 바꾼다.

정말 그럴까? $(i, j)$는 서로 위치가 교환되므로 inversion이 바뀐다. $i$보다 작거나 $j$보다 큰 인덱스는 영향을 받지 않는다. 그리고 $i<k<j$인 인덱스 $k$는 $(i, k)$와 $(k, j)$가 짝을 이루므로 짝수 개 만큼의 inversion이 변화한다.¹ 따라서 호환은 항상 inversion 개수의 홀짝을 바꾼다.

​

ARC 136 B

위 문제의 shift 연산은 $a_{i+1}$과 $a_{i+2}$를 교환, $a_{i+2}$와 $a_i$를 교환하는 2개의 호환으로 표현할 수 있다. 때문에 같은 값이 없다면 shift 연산을 해도 inversion number의 기우성은 불변한다.

불변량을 찾았으니 A와 B의 inversion number를 세는 문제로 바뀌므로 펜윅 트리 등을 사용하면 쉽게 해결할 수 있다. 같은 수가 있다면 shift 연산이 홀짝을 바꿀 수 있어 항상 가능함을 주의해야 한다.

치환

모든 치환은 호환의 합성으로 표현할 수 있다.

치환을 어떻게 표현하든 구성하는 호환 개수의 기우성은 고유하므로, 홀수 개 호환으로 합성된 치환을 홀치환, 반대는 짝치환이라 하자.

​

좀 더 알고리즘적인 표현으로 예시를 들어보겠다. 모든 순열은 적당한 교환들로 표현된다. 어떤 순열이든 trivial한 순열(1, 2, 3…)로부터 교환을 통해 만들 수 있다.

이때 어떠한 순서로 교환하든 전체 교환 개수의 기우성이 변하지 않는다는 걸 알 수 있다.

e.g. (1, 2, 3)에서 (2, 3, 1)을 만들어보라. 2, 4, 6, 8… 무조건 짝수 개의 교환이 필요하다.

​

BOJ 5000 빵 정렬

거의 동일한 문제이지만 중복된 수가 없고 좌표압축도 필요 없다. 이 문제는 순열의 기우성을 이용하면 $O(N)$에 풀린다.

순열의 값 $a_x$에 대해 $f(x)=a_x$를 정의하면 $f(x)$의 합성이 사이클을 가진다는 건 알고리즘 팬들에게 잘 알려진 사실이다. 즉, 순열은 사이클 여러 개로 분할된다.

그런데 사이클 하나도 치환으로 볼 수 있다. 이 치환의 기우성을 잘 살펴보면 전체 치환의 기우성도 알 수 있다. 특히 홀치환의 개수에 집중하자.

주기가 $k$인 사이클을 구성하는 호환의 최소 개수는 $k-1$이므로 짝수 길이 사이클이 홀치환이다. 따라서 짝수 길이 사이클 개수의 홀짝이 곧 순열의 홀짝이다. 이건 $O(N)$으로 간단하게 구해진다.

요약

순열의 기우성은 이를 구성하는 호환 개수의 기우성이자 inversion 개수의 기우성이다.

대칭군과 연관된 내용 같으니 더 깊은 내용이 궁금하다면 군론 책에서 알아보자.