Permutation Cycle Decomposition
Prerequisite
Permutation Cycle Decomposition
순열 싸이클 분할은 말 그대로 순열 $\rm P$ 가 있을 때 이를 엮여있는 부분들로 분할하는 것으로, 더 설명하기에 앞서 순열 싸이클 혹은 순열 그룹이라고 불리는 친구를 살펴보아야 한다.
Permutation Group - 순열 그룹
순열 그룹 $G$ 는 갖고 있는 집합 $M$에 속하는 요소들이 $\sigma(n)$ 를 이용해 이동했을 때 정확히 집합 $M$에 있는 요소들 하나씩 가지게되는 전단사 함수라고 생각할 수 있다.
치환에 $\sigma(n)$ 기호를 쓴다.
예를 들어, <1, 3, 4, 2> 라는 순열 그룹이 있다고 하면, $\sigma(1)=1,~\sigma(2)=3,~\sigma(3)=4,~\sigma(4)=2$ 이고 두 개의 순열 싸이클로 분할할 수 있다.
바로 <1> 과 <3, 4, 2> 인데, 1은 자기 자신으로 반복(싸이클)되고 3, 4, 2는 2 -> 3 -> 4 -> 2 와 같이 싸이클이 생기기 때문에 두개의 순열 싸이클으로 나뉘어졌다.
중요한건, 이렇게 분리된 순열 싸이클에서 서로 다른 싸이클에 있는 원소들은 몇 번을 치환하든 절대 만날 수 없다는 것이다.
이렇게 순열 그룹을 순열 싸이클로 분리해서 풀 수 있는 문제들은 이따 소개할 것이다.
Notation
1. 코시의 두줄 표현법
$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}$
치환의 집합을 $\sigma$ 라고 하면, 각 원소들이 한 번의 치환으로 변경되는 값들을 두 줄로 나열할 수 있다.
순서에 상관없기 때문에 위에서 표현한 것이랑
$\sigma ={\begin{pmatrix}x_{2}&x_{1}&x_{3}&\cdots &x_{n}\\sigma (x_{2})&\sigma (x_{1})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}$
이렇게 표현한 것이랑 같은 순열 그룹을 의미한다.
2. Cycle 표현법
<1, 3, 4, 2> 같은 예시를 다시 보면, (1)(3,4,2) 로 표현하는 것을 Cycle notaiton이나 Cyclic form이라고 한다.
한 자리 수라면 쉼표를 생략하기도 하며 싸이클의 원소가 하나라면 다음과 같이 생략해줄 수도 있다.
(342)
순열 그룹의 합성
순열 그룹 $Q$ 와 $R$ 이 있을 때, 이 두개를 합성할 수 있다.
$Q\cdot R=Q(R(x))$ 라고 볼 수 있고, 어떤 $x$ 가 $R$ 함수를 이용해 먼저 치환된다음에 그 결과값이 $Q$ 에 의해 치환된다고 생각하면 된다.
$ \small \quad Q=\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix} \quad R=\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix} $
라고 할 때,
이다. 일부러 열을 맞춰 $x \to R(x) \to Q(x)$ 로 가는 것이 쉽게 보이도록 했다.
순열 그룹의 합성에서 중요한건, 결합 법칙이 성립한다는 것이다.
교환 법칙은 성립하지 않는다.
순열 그룹의 역함수
전단사 함수는 역함수가 존재하기 때문에 순열 그룹도 역함수를 갖는다.
그리고 이는 각 표현법마다 구하는 법이 있다.
두 줄 표현법에선 1행과 2행의 각 원소가 자리를 바꾼 것으로 생각할 수 있고,
$\small \begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}^{-1}=\begin{pmatrix}2&5&4&3&1\\1&2&3&4&5\end{pmatrix}=\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}$
싸이클 표현법에선 각 싸이클의 원소들을 모두 뒤집으면 된다.
$\left(125\right)^{-1}=\left(521\right)=\left(152\right)$(125)−1=(521)=(152)
순열 그룹의 거듭제곱 🔥
결합 법칙이 성립하기 때문에 순열 그룹 $G$ 를 거듭하여 적용하려는 경우에도 $G$ 자체를 거듭제곱 할 수 있다면 빠르게 결과를 구할 수 있다.
이러한 거듭제곱을 찾는것은 대개 3가지 중 하나의 방법이 쓰이는데, 하나하나 알아보기 전에 공통적으로 쓸 예시를 제시하겠다.
다음과 같은 그룹 $G$ 가 있고, $G^{1,000,000,000}$ 를 찾는다고 하자.
$\small G=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\10&8&5&2&3&1&6&4&7&9\end{pmatrix}=(1,10,9,7,6)(2,8,4)(3,5)$
일단 정답을 보면, $10^9$은 5로 나누었을 때 나머지가 0이므로 첫 번째 그룹은 변하지 않고, 마찬가지로 두 번째 그룹은 1번, 세 번째 그룹도 0번 이동할 것이다.
기존 숫자들이 $G^1$ 를 나타내므로 $G^N$ 은 여기서 $N-1$ 번 연산을 더 거듭한 결과이다.
이처럼 순열 그룹의 크기를 나머지 연산에 이용해 크기를 줄여줄 수 있다.
결과적으로 $G^{1,000,000,000}=\small\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\1&8&3&2&5&6&7&4&9&10\end{pmatrix}$ 이다.
1, 3, 5, 6, 7, 9, 10의 자리는 변하지 않았고 2, 8, 4 는 다음 수로 한 칸씩 치환되었음을 알 수 있다.
1. 싸이클을 직접 찾아 그룹의 크기에 대한 나머지를 이용해 구하는 법
가장 간단한 방법이라고 볼 수 있다.
vi G = {9, 7, 4, 1, 2, 0, 5, 3, 6, 8};
vi vis(10);
vvi groups;
vi result(10);
for (int i = 0; i < sz(G); i++) {
if (vis[i]) continue;
groups.pb({});
int j = i;
do {
vis[j] = 1;
groups.back().pb(j);
j = G[j];
} while (!vis[j]);
}
이렇게 하면 groups 에 모든 분할된 순열 싸이클이 담기게 된다.
이제 $G^M$ 를 찾아보면,
int M = 1'000'000'001;
vi result(10);
for (int i = 0; i < sz(groups); i++) {
for (int j = 0; j < sz(groups[i]); j++) {
result[groups[i][j]] = groups[i][(j + M) % sz(groups[i])];
}
}
올바른 결과가 나오게 된다.
예시로 $G(2)\to8$ 인데, 이것이 속한 그룹은 $(2,\,8,\,4)$ 이므로 $M=1$ 이라면
result[groups[i][j]] = groups[i][(j + M) % g_size]; 라는 코드는 result[2] = [2, 8, 4][2] 이 되므로 result[2] = 8 가 되어 한 번만 이동함을 나타낸다.
실제 코드는 0-based 로 짰지만 설명은 1-based 로 하고 있다.
2. Sparse Table을 이용해 구하는 법
Sparse Table 글을 보면, $f^{2^k}(x)$ 꼴을 전처리해놓고 빠르게 함수형 그래프의 최종 목적지를 찾아내는 테크닉을 설명하는데, 이것이 바로 그것이다.
vi G = {9, 7, 4, 1, 2, 0, 5, 3, 6, 8};
int M = 1'000'000'000;
int LOG = 31;
vvi F(LOG, vi(10));
for (int i = 0; i < 10; i++) F[0][i] = G[i];
for (int k = 1; k < LOG; k++)
for (int i = 0; i < 10; i++)
F[k][i] = F[k - 1][F[k - 1][i]];
vi result(10);
for (int i = 0; i < 10; i++) {
result[i] = i;
for (int k = 0; k < LOG; k++) {
if (M & (1LL << k)) {
result[i] = F[k][result[i]];
}
}
}
3. 빠른 거듭제곱 알고리즘을 이용해 구하는 법
순열을 곱하는 알고리즘은 다음과 같이 만들 수 있다.
auto compose = [](const vi &a, const vi &b) {
vi c(sz(a));
for (int i = 0; i < sz(a); i++)
c[i] = a[b[i]];
return c;
};
이제 이걸 빠른 거듭제곱 알고리즘으로 $O(\log M)$ 에 곱해주면 정답을 찾을 수 있다.
Comments