Home » 같은 것을 포함하는 순열 생성기 (Python)

같은 것을 포함하는 순열 생성기 (Python)

OOO, XX 로 만들 수 있는 5글자 문자열을 모두 생성하는 방법을 소개한다. 총 5개의 글자로 만들 수 있는 순열은 5! (120) 가지이다. 그런데 같은 O 끼리와 같은 X 끼리는 구분할 수 없으므로 실제로는 5!/(3! * 2!) 가지로 10가지의 조합만 가능할 것이다. 파이썬의 itertools 에서는 순열, 조합 및 중복 순열과 중복 조합을 만드는 함수가 제공되지만 같은 것을 포함하는 순열을 생성하는 함수는 제공되지 않는다.

중복된 원소가 있을 때, 중복 없는 순열을 만드는 방법은 다음과 같이 생각해 볼 수 있다. OOOXX 의 5글자로 만들 수 있는 순열의 각 케이스는 다음과 같은 방식으로 결정될 것이다.

  1. 첫번째 글자로 O이나 X 중 하나를 고를 수 있다. 먼저 O를 골랐다면 OOXX로 생성한 순열의 각 단어 앞에 O가 붙게 될 것이다. 반대로 첫 글자로 X를 골랐다면 OOOX 를 사용한 순열의 각 단어 앞에 X를 붙이면 될 것이다.
  2. 즉, (당연히!) 어떤 순서에서 글자를 선택할 때, 앞에서 선택했던 글자를 제외하고 남은 글자만 선택가능하다.

따라서 앞 글자까지 만들어진 단어와, 남아있는 글자들의 각 개수가 주어진다면 그 다음 글자는 남아있는 글자 중에서 각자 다른 것을 하나씩 채택하면 된다. 이 로직은 간단하고 아름답게 재귀적인 방식으로 작성이 가능한데, 재귀로 생성한 결과를 리스트로 리턴하는 것은 부담이 되므로 제너레이터로 만들면 매우 간단해진다. 특히 제너레이터 문법을 사용하면서 재귀적인 흐름을 구현할 때에는 yield from 문법을 적극적으로 사용할 수 있다.

구현 자체는 아주 간단하니 아래에 소개하겠다.

def helper(prefix, ws):
  # prefix : 이전까지 선택된 순열
  # ws: 각 요소와 남은 개수에 해당하는 사전 정보
  # 모든 요소를 소진했을 때 prefix를 리턴한다.
  if all(v == 0 for v in ws.values):
    yield prefix
  # 1개 이상 남은 요소가 있으면 prefix에 추가한다.
  # 해당 요소의 개수를 1차감한 값으로 helper를 다시 호출한다.
  for w in ws:
    if ws[w] > 0:
      yield from helper((*prefix, w), {**ws, w:ws[w]-1})

이 함수를 이용하면 중복 순열을 만드는 함수는 다음과 같이 작성할 수 있다.

from collections import Counter
def perms(xs):
  yield from helper((), Counter(xs))

간단히 다음과 같이 테스트 해 볼 수 있다.

for p in perms('ooxxx'):
  print(''.join(p))

5개 원소의 순열은 5!로 120개 이지만, 이 중 3개와 2개가 구분이 안되므로 5!/(3!*2!)를 계산하면 10개만 나오게 된다.

helper를 내부에 작성해서 전체 코드를 다음과 같이 정리할 수도 있겠다.

from collections import Counter
def perms(xs):
    def helper(prefix, ws):
        if all(v==0 for v in ws.values()):
            yield prefix
        for w in ws:
            if ws[w] > 0:
                yield from helper((*prefix, w), {**ws, w:ws[w]-1})
    yield from helper((), Counter(ws))

댓글 남기기