존슨-트로터 알고리즘

존슨 트로터 알고리즘(Johnson–Trotter algorithm)은 모든 순열을 중복 없이 한 번씩 생성하는 순열 생성 알고리즘 중 하나로, 인접한 원소의 교환을 통해 다음 순열을 만들어낸다.

1 개요

존슨 트로터 알고리즘은 1963년 Selmer M. Johnson과 Hale F. Trotter가 제안한 알고리즘으로, n개의 원소에 대해 서로 다른 모든 순열을 중복 없이 생성할 수 있도록 설계되었다. 이 알고리즘은 각 원소에 방향을 부여하고, '이동 가능한 원소'를 반복적으로 찾아 이들을 인접한 원소와 교환하는 방식으로 동작한다. 특히 한 번에 하나의 원소만 이동시키므로, 각 순열 간의 차이는 항상 두 원소의 위치 교환으로 이루어진다.

2 작동 원리

존슨 트로터 알고리즘은 다음과 같은 규칙을 따른다:

• 각 숫자는 좌 또는 우 중 하나의 방향을 가진다.
• '이동 가능한 숫자'는 자신이 가리키는 방향의 이웃 숫자보다 작아야 한다.
• 가장 큰 이동 가능한 숫자를 찾아, 그 숫자를 가리키는 방향으로 이동시킨다.
• 숫자가 이동된 후, 자신보다 큰 모든 숫자의 방향을 반대로 전환한다.

3 알고리즘 절차

1. 초기 상태: 각 숫자에 왼쪽 방향(<-)을 부여한다.
2. 가장 큰 이동 가능한 숫자 M을 찾는다.
3. M을 가리키는 방향으로 인접한 숫자와 교환한다.
4. M보다 큰 숫자들의 방향을 반대로 전환한다.
5. 더 이상 이동 가능한 숫자가 없을 때까지 2~4단계를 반복한다.

4 예시

3개의 숫자 {1, 2, 3}에 대해 알고리즘이 생성하는 순열의 과정을 아래와 같이 정리할 수 있다. 각 숫자는 초기 상태에서 왼쪽(<-)을 가리키며, 방향은 괄호 안에 표시된다.

단계	상태	설명
1	1(←) 2(←) 3(←)	초기 상태
2	1(←) 3(←) 2(←)	2가 이동 가능 → 2와 3 교환
3	3(←) 1(←) 2(←)	3이 이동 가능 → 3과 1 교환
4	3(←) 2(←) 1(←)	2가 이동 가능 → 2와 1 교환
5	2(→) 3(→) 1(←)	3 이동 후 방향 반전
6	2(→) 1(→) 3(→)	3이 이동 가능 → 3과 1 교환
7	종료	더 이상 이동 가능한 숫자 없음

최종적으로 생성된 순열 목록:

1. [1, 2, 3]
2. [1, 3, 2]
3. [3, 1, 2]
4. [3, 2, 1]
5. [2, 3, 1]
6. [2, 1, 3]

5 시간 복잡도

• 시간 복잡도: O(n!) (총 순열의 수)
• 각 단계는 O(n) 시간 내에 수행 가능하므로 전체 알고리즘은 O(n·n!) 시간 복잡도를 갖는다.

6 응용

• 중복 없이 모든 순열을 생성해야 하는 경우
• 퍼즐 문제 또는 백트래킹 문제에서의 순열 탐색
• 그래프 이론, 조합론, 계산기하학에서 순열의 나열이 필요한 경우

7 같이 보기

• 순열
• 백트래킹
• 그래이 코드
• 조합론
• 힙의 순열 알고리즘

8 참고 문헌

• Johnson, S. M., & Trotter, H. F. (1963). "Generating permutations by adjacent transposition". Mathematics of Computation, 17(83), 282–285.