파이썬에서 주어진 조건을 만족하는 모든 순열의 개수를 찾는 프로그램

1부터 n까지의 모든 원소를 포함하는 집합 A가 있다고 가정해 보겠습니다. P(A)는 집합 A의 원소들로 만들 수 있는 모든 순열(permutation)의 집합을 의미합니다. 이번 문제의 목표는 P(A)에 속한 순열 중에서 주어진 조건들을 만족하는 것의 개수를 구하는 것입니다.

문제의 조건

P(A)의 순열은 다음 두 가지 조건을 만족해야 합니다.

조건 1: 범위 [1, n]의 모든 i에 대해 A[i] ≠ i 입니다. 즉, 어떤 원소도 자기 자신의 위치에 있으면 안 됩니다(완전 순열, derangement).
조건 2: k개의 인덱스로 이루어진 집합 {i1, i2, ..., ik}가 존재하여, 모든 j < k에 대해 A[ij] = ij+1이고 마지막에 A[ik] = i1을 만족해야 합니다. 즉, 길이가 정확히 k인 순환(cycle) 구조가 하나라도 존재해야 합니다.

예제로 이해하기

n = 3, k = 2가 입력으로 주어지면 출력은 0이 됩니다. 그 이유를 단계별로 살펴보겠습니다.

배열의 인덱스는 1부터 시작한다고 가정합니다. N = 3이고 K = 2이므로, 첫 번째 조건(A[i] ≠ i)을 만족하는 순열은 [3, 1, 2]와 [2, 3, 1] 두 가지뿐입니다. 한편 K = 2일 때 가능한 인덱스 쌍은 [1,2], [1,3], [2,3], [2,1], [3,1], [3,2]의 6가지입니다.

P(A) → [3, 1, 2]를 검증하면:

[1, 2]: A[1] ≠ 2
[1, 3]: A[1] = 3이지만 A[3] ≠ 1
[2, 3]: A[2] ≠ 3
[2, 1]: A[2] = 1이지만 A[1] ≠ 2
[3, 1]: A[3] = 1이지만 A[1] ≠ 3
[3, 2]: A[3] ≠ 2

P(A) → [2, 3, 1]을 검증하면:

[1, 2]: A[1] = 2이지만 A[2] ≠ 1
[1, 3]: A[1] ≠ 3
[2, 3]: A[2] = 3이지만 A[3] ≠ 2
[2, 1]: A[2] ≠ 1
[3, 1]: A[3] = 1이지만 A[1] ≠ 3
[3, 2]: A[3] ≠ 2

두 순열 모두 길이 2의 순환을 갖지 않으므로, 조건을 만족하는 순열은 없으며 최종 결과는 0입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

ps := [1, n] 범위의 원소로 만들 수 있는 모든 순열 목록
c := 0 (조건을 만족하는 순열의 개수)
ps의 각 순열 p에 대해 다음을 수행합니다.
- p의 각 인덱스 i와 값 a를 확인하여 a == i인 경우(고정점 존재) 반복문을 빠져나갑니다. 해당 순열은 조건 1을 위반하므로 제외됩니다.
- 고정점이 없다면, j를 0부터 n-1까지 반복하며 다음을 수행합니다.
  - current := p[j], cycle_length := 1로 초기화합니다.
  - current != j인 동안 current := p[current]로 갱신하고 cycle_length를 1씩 증가시켜, j가 속한 순환의 길이를 계산합니다.
  - cycle_length == k이면 c를 1 증가시키고 반복문을 빠져나갑니다.
모든 순열을 확인한 후 c를 반환합니다.

여기서 핵심 아이디어는 임의의 순열이 서로 겹치지 않는 여러 개의 순환(cycle)으로 분해될 수 있다는 점입니다. 따라서 각 위치에서 출발해 순환의 길이를 추적하면, 길이가 정확히 k인 순환이 존재하는지 판별할 수 있습니다.

구현 예제

아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.

import itertools

def solve(n, k):
   ps = itertools.permutations(range(n), n)
   c = 0
   for p in ps:
      for i, a in enumerate(p):
         if a == i:
            break
      else:
         for j in range(n):
            current = p[j]
            cycle_length = 1
            while current != j:
               current = p[current]
               cycle_length += 1
            if cycle_length == k:
               c += 1
               break
   return c

n = 3
k = 2
print(solve(n, k))

입력

3, 2

출력

코드 핵심 포인트

itertools.permutations: range(n)의 모든 순열을 손쉽게 생성합니다. 내부적으로는 0 기반 인덱스를 사용하지만, 로직상 결과에는 차이가 없습니다.
for-else 문: 파이썬의 독특한 문법으로, 반복문이 break 없이 정상 종료되었을 때 else 블록이 실행됩니다. 여기서는 '고정점이 없는 경우'를 깔끔하게 처리하는 데 활용됩니다.
순환 길이 계산: while 루프를 통해 현재 위치에서 출발하는 순환의 길이를 구하고, 이 값이 k와 일치하는지 확인합니다.