사전식 순열생성

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

사전식 순열 생성 함수

주어진 수열에 대해 모든 순열을 생성하는 방법에는 많은 종류가 있다. 그 중 한가지 고전적인 알고리듬은 사전식 순서에 의한 다음 순열을 찾는 방법이다. 이 방식을 사용할 수 있다면 (중복된 원소가 있더라도) 각각 고유한 순열들의 멀티셋을 한 번에 하나씩 생성할 수 있다.

먼저 수열을 오름차순으로 정렬한다. (이는 사전식 순열의 맨 첫째 순열에 해당한다.) 그런다음 현재 순열보다 큰 바로 다음 순열을 찾아나간다. 그리고 더 이상 큰 순열을 찾을 수 없다면 종료하면 된다. 이 방식은 14세기 인도의 나라야나 판디타에 의해 고안되었다.

아래 알고리듬은 주어진 순열에 대해 바로 다음 번 사전식 순열을 찾아 제자리 교환을 한다.

  1. a[k] < a[k+1] 인 가장 큰 인덱스 k를 찾는다. 만약 이를 찾을 수 없다면 탐색을 종료한다.
  2. k이후 a[k]보다 큰 값을 가진 가장 먼 인덱스를 찾는다. (a[k] < a[l])
  3. k와 l위치의 값을 교환한다.
  4. 그런다음 k+1 에서 마지막 인덱스 사이를 역순으로 만든다.

위 알고리듬에 의해 (1, 2, 3, 4)의 값의 사전식 순열을 찾아보자.

  1. 첫번째 k는 2이다.(a[2]==3 < 4)
  2. 그리고 l은 3이다 (a[3]==4)
  3. 두 값을 교환한다. (a == (1, 2, 4, 3))
  4. a[:3]을 뒤집는다.

이 과정을 거쳐서 a는 (1, 2, 4, 3)이 되었다. 한 번 더 해보자.

  1. k는 1이다.
  2. l은 3이다.
  3. 두 값을 교환하면 a는 (1, 3, 2, 4)이 된다.
  4. 2이후의 인덱스들의 값을 교환한다.

이제 a는 (1, 3, 2, 4)가 된다.

다음은 이 로직의 파이썬 구현이다.


# Narayana Pandita's lexicographical permutation def permutation(iterable): k = 0 l = 0 pool = tuple(iterable) n = len(pool) indices = range(n) # find k yield tuple((pool[x] for x in indices)) while True: k = -1 r = 0 while r < n-1: if indices[r+1] > indices[r]: k = r r += 1 if k < 0: raise StopIteration for r in range(k+1, n): if indices[r] > indices[k]: l = r indices[k], indices[l] = indices[l], indices[k] indices[k+1:] = sorted(indices[k+1:]) yield tuple((pool[x] for x in indices[:2])) a = "1234" for i in permutation(a): print "".join(i)