콘텐츠로 건너뛰기
Home » 사전식 순열의 다음 항 구하기 (파이썬)

사전식 순열의 다음 항 구하기 (파이썬)

참고 : 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]에 이르게 될 것이다.

이러한 순열과 관련하여서는 itertools.permutations()를 사용하거나 N번째 순열을 찾는 함수는 여러 번 소개한 적이 있다. 오늘은 임의의 순열이 주어졌을 때 그 다음 번 순열을 찾아야 하는 문제로 좀 차이가 있다. 이는 특정한 상태로부터 그 다음 상태의 사전식 순열을 찾는 알고리듬이 필요하다는 뜻이다.

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

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

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

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

한 번 더 해보자.

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

이 방법은 잘 작동하는 것 같다. 그럼 이를 코드로 구현해보자.

# Narayana Pandit's lexicographical permutation
from typing import List, Any
def nextPermutation(xs: List[Any]):
    k = max(i for (i, x) in enumerate(xs[:-1]) if x < xs[i+1])
    l = max(k + i for (i, x) in enumerate(xs[k:]) if x >= xs[k])
    xs[k], xs[l] = xs[l], xs[k]
    xs[k+1:] = xs[:k:-1]

그런데 xs가 내림차순으로 정렬된 상태(사전식 순열의 마지막)라면 k 값을 구할 수 없게 된다. max()함수에 빈 인자가 전달되기 때문에 ValueError가 발생한다. 따라서 이 때에는 다시 뒤집어서 내림차순으로 정렬된 상태로 만들어주면 된다.

def nextPermutation(xs: List[Any]):
    k = len(xs) - 2
    try:
        k = max(i for (i, x) in enumerate(xs[:-1]) if x < xs[i+1])
    except ValueError:
        xs[:]= xs[::-1]
        return
    l = max(k + i for (i, x) in enumerate(xs[k:]) if x >= xs[k])
    xs[k], xs[l] = xs[l], xs[k]
    xs[k+1:] = xs[:k:-1]

이제 이 함수를 사용해서 주어진 연속열의 순열을 차례로 생성해주는 제너레이터 함수를 작성해보자. itertools.permutations 함수와 하는 일이 거의 같다.

from typing import Iterable, Any
def permutations(xs: Iterable):
    ws = list(xs)
    while True:
        try:
            yield ws[:]
            k = max(i for (i, (x, y)) in enumerate(zip(ws, ws[1:])) if x < y)
            l = max(k + i for (i, x) in enumerate(ws[k:]) if x >= ws[k])
            ws[k], ws[l] = ws[l], ws[k]
            ws[k+1:] = ws[:k:-1]
        except Exception as e:
            print(e)
            return

태그: