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

sooopd

2년 ago

주어진 원소로 가능한 순열/조합을 생성하는 기능은 표준 라이브러리 내 itertools 모듈을 통해 사용할 수 있다. (참고로 단순히 순열 조합을 생성하는 방법은 의외로 간단해서 직접 구현해서 사용해도 된다.) 그런데 가끔 볼 수 있는 문제 중에는 같은 원소가 여러 개 있을 때의 순열을 구하는 문제가 있다. 이 문제는 한 개씩 있는 원소를 중복해서 순열/조합을 만드는 중복순열, 중복조합과는 달리 사용가능한 원소가 중복은 되지만 그 개수에 제한이 있다는 것이다. 흔히 “같은 것을 포함하는 순열”이라고 하던데, 오늘은 이처럼 같은 원소를 여러 개 포함하는 순열을 만드는 방법에 대해서 알아보자.

예를 들어 2종류의 기호 O,O,O, X,X 로 만들 수 있는 5글자 문자열을 모두 생성하는 경우를 보자. 서로 다른 5개의 글자로 만들 수 있는 순열은 5! (120) 가지이다. 그런데 문제와 같이 같은 글자가 여럿있는 경우, 같은 O 끼리는 순서를 바꾸어도 결국 같은 것으로 취급되기 때문에 이러한 경우는 제외해야 한다. 3개의 O가 순서를 바꾼 3!(=6)개 만큼의 경우는 중복으로 쳐야 할 것이고, 2개의 X에 대해서도 순서가 바뀐 것을 중복으로 보고 셈에서 제외해야 한다. 결국, 구분할 수 없는 요소들간의 순열수만큼 전체 순열 수를 나눠야 하므로, 실제로는 5!/(3! * 2!) = 10 가지의 조합만 가능할 것이다.

중복된 원소가 있을 때, 중복 없는 순열을 만드는 방법은 다음과 같이 생각해 볼 수 있다. 각각의 단어는 다음과 같은 로직에 의해서 결정될 수 있다.

3개의 X와 2개의 O가 있고, 우리는 맨 먼저 O나 X 중 하나를 고를 수 있다. O를 골랐다면 1개의 O와 3개의 X가, X를 골랐다면 2개의 O와 2개의 X가 남게된다.
첫글자가 O라면, 나머지 4개로 만든 단어의 순열에서 각 단어 앞에 O를 붙이면 된다. 반대로 첫글자가 X라면 나머지 4개로 만든 순열에서 앞에 X를 붙이면 된다.
두 번째, 세 번째 글자를 고르는 과정에 1번과 마찬가지로 ‘개수가 남아있는’ 글자 중에서 하나를 골라, 이 앞단계에서 결정된 단어 뒤에 붙인다. 그리고 이 앞부분이 이제 남은 순열에 각각 붙으면 된다.
단어가 원하는 길이가 되면 결정된 것으로 본다.

따라서 현재 단계의 직전까지 정해진 단어의 앞부분(prefix)와 남은 각각의 글자의 개수에 대한 정보가 있다면 재귀적으로 이 문제를 풀 수 있다. 순열/조합 생성기와 마찬가지로 재귀로 구현된 제너레이터를 사용하여 쉽게 구현할 수 있다.

from collections import Counter

def helper(prefix, es, n):
  # prefix : 이전까지 선택된 원소들
  # es : 남아있는 선택가능한 원소들과 각 원소의 개수
  # n : 더 추가해야 하는 원소의 수
  if n == 0:  # prefix가 각 조합의 길이가 되었다면 반환한다.
    yield prefix
    return
  # 남아있는 각 원소에서 하나를 뽑아 prefix 뒤에 추가하고 이 정보로 helper를 호출한다.
  for el, cnt in es.items():
    yield from helper((*prefix, el), {**es, el:cnt-1}, n - 1))

def perms_with_dups(xs, /, n=None):
  if n is None:
    n = len(xs)
  yield from helper(xs, Counter(xs), n)

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

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

앞서 문제에서와 같이 10개의 결과가 출력되며, 똑같은 결과는 하나도 존재하지 않는다는 결론을 얻을 수 있다. 다른 문제를 한 번 보자. A, B, C 알파벳을 각각 최대 3개씩 사용해서 만들 수 있는 5글자 짜리 단어는 몇 개일까?

xs = list('AAABBBCCC')
for i, p in enumerate(perms(xs, 5)):
    print(f'{i+1:3d}:', ''.join(p))

Share this: