설명
- 순열을 생성하는 여러 알고리즘 중에서 사전식 순서(lexicographic order)를 표현한다.
- 여기서는 사전식 순서에 따라 오름차순으로 순열을 표현한다.
- 숫자와 문자 그리고 색깔로 표현할 수 있다.
- 순열의 길이가 커짐에 따라 모든 순열을 표현하는 데 걸리는 시간이 급격히 늘어남을 체감할 수 있다.
알고리즘
예를들어, 네 알파벳 a, b, c, d를 abcd, abdc, acbd, ... 순서로 표현한다. 각각의 순열에서 알파벳이 위치한 자리를 왼쪽부터 차례대로 1, 2, 3, 4번이라 하자.
- 첫 번째, abcd에서 오른쪽부터 거꾸로 셀 수 있는 오름차순의 최대 부분순열은 d로써 길이는 1이다.
- 다음 순열에서는 3번 c가 자신 뒤의 알파벳으로 교체되어야 한다.
- 또한, 3번 앞의 번호들은 제자리를 지켜야하고, 3번 뒤의 번호들은 알파벳순으로 나열된다.
- 따라서, 3번의 c는 3번 이후의 알파벳 중에서 c 뒤로 가장 빠른 d로 교체된다.
- 두 번째, abdc에서 오른쪽부터 거꾸로 셀 수 있는 오름차순의 최대 부분순열은 dc로써 길이는 2다.
- 다음 순열에서는 2번 b가 자신 뒤의 알파벳으로 교체되어야 한다.
- 또한, 2번 앞의 번호들은 제자리를 지켜야하고, 2번 뒤의 번호들은 알파벳순으로 나열된다.
- 따라서, 2번의 b는 2번 이후의 알파벳 중에서 b 뒤로 가장 빠른 c로 교체된다.
- 세 번째, acbd에서 오른쪽부터 거꾸로 셀 수 있는 오름차순의 최대 부분순열은 d로써 길이는 1이다.
- 다음 순열에서는 3번 b가 자신 뒤의 알파벳으로 교체되어야 한다.
- 또한, 3번 앞의 번호들은 제자리를 지켜야하고, 3번 뒤의 번호들은 알파벳순으로 나열된다.
- 따라서, 3번의 b는 3번 이후의 알파벳 중에서 b 뒤로 가장 빠른 d로 교체된다.
- 이와 같은 방법으로 오른쪽부터 거꾸로 셀 수 있는 오름차순의 최대 부분순열의 길이가 본래 순열의 길이 4가 될 때까지 반복하면, 사전식 순서로 모든 순열이 차례대로 나타난다.