스테인하우스-존슨-트로터 알고리즘

스테인하우스-존슨-트로터 알고리즘(Steinhaus–Johnson–Trotter algorithm) 또는 존슨-트로터 알고리즘(Johnson–Trotter algorithm)은 플레인 변경(plain changes)으로도 불리는 순열(permutohedron) 알고리즘으로 n 개 요소의 모든 순열을 생성하는 후고 스테인하우스(Hugo Steinhaus), 셀먼 존슨(Selmer M. Johnson) 및 헤일 트로터(Hale F. Trotter)의 이름을 따서 명명된 알고리즘이다. 생성하는 시퀀스의 각 순열들은 시퀀스의 인접한 두 요소를 교체하며 이전 순열과 다르다. 마찬가지로 이 알고리즘은 또한 순열(permutohedron)에서 해밀턴 경로(Hamiltonian path)주기를 찾는다.

예


서로 다른 알고리즘에 의해 생성된 길이(n)4의 순열의 순서. 순열은 색상으로 구분된다. 여기서 1 = 빨간색, 2 = 노란색, 3 = 녹색, 4 = 파란색

같이 보기

힙 알고리즘 (Heap's algorithm)

각주