존슨-트로터 알고리즘

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

개요

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

작동 원리

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

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

알고리즘 절차

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

예시

• [1, 2, 3, 4]
• [1, 2, 4, 3]
• [1, 4, 2, 3]
• [4, 1, 2, 3]
• [4, 1, 3, 2]
• [1, 4, 3, 2]
• [1, 3, 4, 2]
• [1, 3, 2, 4]
• [3, 1, 2, 4]
• [3, 1, 4, 2]
• [3, 4, 1, 2]
• [4, 3, 1, 2]
• [4, 3, 2, 1]
• [3, 4, 2, 1]
• [3, 2, 4, 1]
• [3, 2, 1, 4]
• [2, 3, 1, 4]
• [2, 3, 4, 1]
• [2, 4, 3, 1]
• [4, 2, 3, 1]
• [4, 2, 1, 3]
• [2, 4, 1, 3]
• [2, 1, 4, 3]
• [2, 1, 3, 4]

시간 복잡도

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

응용

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

같이 보기

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

참고 문헌

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