사전식 순열의 다음 항 구하기

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

사전식 순열 생성 함수

어떤 원소들의 순열을 구하는 많은 알고리듬이 있다. 파이썬의 itertools 모듈은 순열, 조합 생성을 하는 permutations(), combinations() 등의 함수를 제공한다. 이 블로그에서도 이 외에 특정한 집합에 대해 N 번째 순열을 구하는 문제도 다뤄본 적이 있다. 오늘은 특정한 수열이 주어졌을 때, 해당 수열의 원소들로 구성되는 사전식 순열에서 다음 번 순열을 구하는 문제를 생각해보자.

사전식 순열이란 특정 집합의 원소들로 이루어진 모든 순열을 정렬하여 순차적으로 나타내는 순열을 말하는 것이다. 예를 들어 [1,2,3,4]는 오름차순으로 정리되어 있으므로 사전식 순열에서는 가장 처음에 등장한다. 그리고 그 다음은 [1,2,4,3], [1,4,2,3], [1,4,3,2], … 의 순으로 진행하여 [4,3,2,1]에 이르게 될 것이다.

다른 예를 들어보자. 1에서 6까지의 6개의 자연수로 만들 수 있는 순열의 수는 모두 720(6!)가지이다. 이 중에서 [4, 1, 5, 3, 2] 의 바로 다음 번에 나타나는 순열은 무엇일까? (답은 [4, 2, 1, 3, 5] 이다.) 이 질문에 답할 수 있는 알고리듬은 이미 14세기에 인도의 수학자 나라야나 판디타가 고안한 것이 있다.

  1. a[k] < a[k+1] 인 가장 큰 인덱스 k를 찾는다. 만약 이를 찾을 수 없다면, 수열이 역순으로 정렬된 것으로 사전식 순열의 맨 마지막 항이 될 것이다.
  2. k를 찾았다면 k이후의 인덱스에서 a[k]보다 큰 값을 가진 가장 먼 인덱스 l을 찾는다.
  3. kl위치의 값을 교환한다.
  4. 그런다음 k보다 다음 위치의 값들만 역순으로 재배치한다.

위 알고리듬에 의해 [4, 1, 5, 3, 2] 의 값의 다음 번 순열을 찾아보자.

  1. 증가하는 마지막 인덱스는 1이다. (a[1] => 1)
  2. 1보다 큰 값을 가지는 가장 먼 인덱스는 4이다. (a[4] => 2)
  3. 1과 4 자리의 값을 바꾼다. ([4, 2, 5, 3, 1])
  4. 1다음의 3개 숫자를 역순으로 뒤집는다. ([4, 2, 1, 3, 5])

한 번 더 해보자.

  1. 증가하는 마지막 인덱스는 3이다. (a[3] => 3)
  2. 3보다 큰 값을 가지는 가장 먼 인덱스는 4이다. (a[4] => 5)
  3. 1과 4 자리의 값을 바꾼다. ([ 4, 2, 1, 5, 3 ])
  4. 1다음의 3개 숫자를 역순으로 뒤집는다. ([ 4, 2, 1, 5, 3 ])

이런 식으로 사전식 순열에서 임의의 순번에 해당하는 순열의 다음 번 순열을 찾아낼 수 있다.

다음은 이 로직의 파이썬 구현이며, 인자로 주어진 리스트를 제자리에서 변형하게 된다.

# Narayana Pandit's lexicographical permutation
from typing import List, Any


def permutations(xs: List[Any]):
    try:
        k = max(k for k in range(len(xs)-1)
                if xs[k] < xs[k+1])
    except ValueError:
        return
    m = max((i, xs[i]) for i in range(len(xs))
            if i > k and xs[i] > xs[k])[0]
    xs[k], xs[m] = xs[m], xs[k]
    xs[k+1:] = xs[:k:-1]


if __name__ == '__main__':
    a = [1, 2, 3, 4]
    for i in range(24):
        print(a)
        permutations(a)

[1, 2, 3, 4]에 대해서 반복적으로 이 함수를 적용하면 사전식 순열이 되어 차례로 출력되는 것을 확인할 수 있다.