표준 라이브러리 itertools를 사용하면 주어진 집합의 원소로 만들 수 있는 모든 순열과 조합을 생성해 볼 수 있다. 이 모듈은 순열, 조합, 중복조합에 관한 제너레이터 함수를 제공하지만, 좀 더 개별적인 케이스에서 활용할 수 있는 함수는 제공해주지 않는 아쉬움이 있다. 예를 들면 중복 순열(사실 중복 순열은 itertools.product()를 활용해서 구할 수 있다.)이라든지, 이 글에서 설명하고자 하는 같은 것을 포함하는 순열을 만드는 경우가 이에 해당한다.
예를 들어 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가 남게된다.
- 이미 2개의 O를 모두 골랐다면 ‘O’의 개수는 0이며, 더 이상 ‘O’를 고를 수 없다. 잔여수량이 남아있는 원소중에서만 고르도록 한다.
조합 생성기를 작성할 때에는 앞서서 고른 원소는 다시 고르지 못하는 것이었지만, 여기서는 순서를 유지해야하므로 고를 수는 있어야 한다. 다만 중복되는 원소들끼리는 구분을 하지 않는 것이 중요한데, 이를 구현하기 위해서는 각각의 중복되는 원소들을 개별 아이템으로 취급하지 않고 (원소, 잔여개수)의 쌍으로 보는 것이 필요하다. 따라서 중복되는 원소를 포함하는 집합 전체는 카운터(collections.Counter)로 만들고, 여기서 각각의 원소를 고르도록 하면 된다. 주의할 점은 더 이상 고를 수 없는 원소는 고르지 않도록 해야 한다는 것이다.
그렇게해서 중복된 원소를 포함하는 집합에서 순열을 구하는 함수도 아래와 같이 아름답고 짧게 작성된다.
from collections import Counter
def permutations_along_dups(ns, k=None):
def helper(head, es, k):
if k == 0:
yield head
for el, cnt in es.items():
# 만약 모두 소진한 요소라면 더 이상 추가하지 않는다.
if cnt == 0:
continue
yield from helper((*head, el), {**es, el:cnt - 1}, k-1)
yield from helper(tuple(), Counter(ns), len(ns) if k is None else k)
for i, x in enumerate(permutations_along_dups(list('aaabb'))):
print(i + 1, x)
# 1 ('a', 'a', 'a', 'b', 'b')
# 2 ('a', 'a', 'b', 'a', 'b')
# 3 ('a', 'a', 'b', 'b', 'a')
# 4 ('a', 'b', 'a', 'a', 'b')
# 5 ('a', 'b', 'a', 'b', 'a')
# 6 ('a', 'b', 'b', 'a', 'a')
# 7 ('b', 'a', 'a', 'a', 'b')
# 8 ('b', 'a', 'a', 'b', 'a')
# 9 ('b', 'a', 'b', 'a', 'a')
# 10 ('b', 'b', 'a', 'a', 'a')