순열 사이클 분할에 대해 알아보기

1. 순열 사이클 1부터 n까지 정수 n개로 이루어진 배열을 순열이라고 부른다. 예를 들어 [3,2,4,5,1]은 길이가 5인 순열이다. 배열의 인덱스를 '현재 위치', 배열의 값을 '다음에 갈 곳'으로 생각하고 인덱스 > 값으로 향하는 방향 그래프를 만들 수 있다. 즉, [3,2,4,5,1]은 1 > 3, 2 > 2, 3 > 4, 4 > 5, 5 > 1로 간선을 이으면 다음과 같이 방향 그래프를 만들 수 있다. 위 그래프는 2개의 사이클 1 > 3 > 4 > 5, 2 > 2가 있다. 이 사이클들을 순열 사이클이라고 부른다. 전체 순열을 여러개의 독립적인 순열 사이클로 분할하는 것을 '순열 사이클 분할'이라고 부른다. 길이 n인 순열에는 반드시 사이클이 생긴다. 왜냐하면 먼저 1부터 n까지 1개씩만 ..