존슨-트로터 알고리즘 편집하기

존슨 트로터 알고리즘(Johnson–Trotter algorithm)은 모든 순열을 중복 없이 한 번씩 생성하는 순열 생성 알고리즘 중 하나로, 인접한 원소의 교환을 통해 다음 순열을 만들어낸다.
==개요==
존슨 트로터 알고리즘은 1963년 Selmer M. Johnson과 Hale F. Trotter가 제안한 알고리즘으로, n개의 원소에 대해 서로 다른 모든 순열을 중복 없이 생성할 수 있도록 설계되었다. 이 알고리즘은 각 원소에 방향을 부여하고, '이동 가능한 원소'를 반복적으로 찾아 이들을 인접한 원소와 교환하는 방식으로 동작한다. 특히 한 번에 하나의 원소만 이동시키므로, 각 순열 간의 차이는 항상 두 원소의 위치 교환으로 이루어진다.
==작동 원리==
존슨 트로터 알고리즘은 다음과 같은 규칙을 따른다:
*각 숫자는 좌 또는 우 중 하나의 방향을 가진다.
*'이동 가능한 숫자'는 자신이 가리키는 방향의 이웃 숫자보다 작아야 한다.
*가장 큰 이동 가능한 숫자를 찾아, 그 숫자를 가리키는 방향으로 이동시킨다.
*숫자가 이동된 후, 자신보다 큰 모든 숫자의 방향을 반대로 전환한다.
==알고리즘 절차==
#초기 상태: 각 숫자에 왼쪽 방향(<-)을 부여한다.
#가장 큰 이동 가능한 숫자 M을 찾는다.
#M을 가리키는 방향으로 인접한 숫자와 교환한다.
#M보다 큰 숫자들의 방향을 반대로 전환한다.
#더 이상 이동 가능한 숫자가 없을 때까지 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.
==각주==
[[분류:알고리즘]]