[clearfix]
1. 개요
순열 생성 알고리즘(algorithm for generating permutations)은 치환의 결과를 사전식 순서에 따라 오름차순(또는 내림차순 등의 기준)으로 출력하는 알고리즘이다. 이때 '사전식 순서'는 순열(permutation)이며 순열 생성 알고리즘으로 나오는 목록의 수는 하강 계승 [math(n^{\underline r})]의 결괏값이다.[1] 따라서 만약 주어진 원소 수와 배열 자리수가 같다면 팩토리얼 n!이다.[2]2. 순열 생성 알고리즘들
H. F. 트로터(H. F. Trotter)가 1962년에 발표한 알고리즘115(algorithm115), 셀머 존슨(Selmer M. Johnson)이 1963년에 발표한 존슨 알고리즘(Johnson algorithm), B. R. 히프(B. R. Heap)가 발표한 힙 알고리즘(Heap algorithm) 등이 있다. [3][4][5]특히 힙 알고리즘은 로버트 세지윅(Robert Sedgewick)이 1977년 제안한 바와 같이 현대 컴퓨터 프로그램 언어에서 순열생성 알고리즘으로 개량된 버전들이 잘 사용되고 있다.[6] [7]
3. 군론
군론에서 치환군(순열군) {1,2,3}을 순열 생성 알고리즘을 사용해서 조사해보면 (123), (132), (231), (312), (213), (321) 6개가 빠르게 나온다.즉, [math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix})]을 쉽게 얻을 수 있다.
[1]
대다수의 고등학교 재학생/졸업생이라면
고등학교 수학에서 나오는 표기인 [math({}_n\mathrm P_r)]이 더 친숙할 것이다.
[2]
[math(n^{\underline n} = \dfrac{n!}{0!} = n!)]
[3]
article Free Access, Algorithm 115: Perm, Author: H. F. Trotter, Communications of the ACM, Volume 5 Issue 8 Aug. 1962 pp 434–435 doi:10.1145/368637.368660 Online:01 August 1962 Publication History
https://dl.acm.org/doi/10.1145/368637.368660
[4]
journal article, Generation of Permutations by Adjacent Transposition, Selmer M. Johnson, Mathematics of Computation, Vol. 17, No. 83 (Jul., 1963), pp. 282-285 (4 pages), Published By: American, Mathematical Society, Mathematics of Computation, doi:10.2307/2003846
https://www.jstor.org/stable/2003846
[5]
Permutations by interchanges By B. R. Heap, The Computer Journal, Volume 6, Issue 3, November 1963, Pages 293–298,
https://doi.org/10.1093/comjnl/6.3.293 Published:01 November 1963
[6]
article Free Access, Permutation Generation Methods, Author: Robert Sedgewick, ACM Computing Surveys, Volume 9 Issue 2. June 1977 pp 137–164
https://doi.org/10.1145/356689.356692 Online:01 June 1977 Publication History
[7]
러스트(Rust) -permutohedron()
https://docs.rs/permutohedron/latest/permutohedron/ heap_recursive: Heap's algorithm for generating permutations, recursive version.