특정한 원소를 가지고 만들 수 있는 모든 순열/조합을 생성하려는 경우, 기본적으로는 itertools 모듈을 사용한다. combinations() 는 생성 가능한 모든 조합을 만드는 제너레이터 함수이며, permutations() 는 생성 가능한 모든 순열을 만들어내는 제너레이터이다. 중복 조합의 경우에는 combinations_with_replacement() 라는 다소 장황한 이름의 제너레이터가 있다. 중복 순열이 조금 애매한데, 중복 순열은 원래 원소의 집합에 대한 N번의 데카르트 곱으로 만들어진다. 그래서 product() 함수를 사용해서 약간 돌려서(?) 이용한다.
오늘은 순열, 조합, 중복조합, 중복순열을 각각 생성하는 제너레이터를 직접 구현하는 방법을 소개하겠다. 실제로 기본적인 아이디어는 동일한데, 파이썬에서 제너레이터를 재귀적으로 사용할 수 있게 해주는 yield from 문법을 사용하기 때문에 구현도 매우 간단하고 성능도 좋은 편이다. 재귀 깊이에 대한 제한은 동일하게 적용되지만, 대신 매번 순열/조합을 생성하는 방식이기 때문에 메모리 스루풋도 나쁘지 않은 편이다.
순열을 생성하는 제너레이터
순열을 생성하는 제너레이터가 이 아이디어의 가장 기본이 된다. (a1, a2, a3, a3, ..., an) 으로 구성된 n개의 원소중에서 k를 골라 만들 수 있는 순열을 생성한다고 해보자. 이 때 과정은 다음과 같다.
- 먼저 첫번째 값을 골라야 한다. 첫번째 값은 a1 ~ an 중에서 하나를 고르는데, 순서대로 고르므로 a1부터 고른다. 이후 고르는 원소들로 두 번째, 세 번째 값을 붙여나가 순열을 만들 것이다. a1 으로 시작한 순열을 모두 생성한 후에는 a2를 고르는 식이다.
- 두 번째 값을 고를 때에는 첫 번째로 고른 값을 제외하고 남은 원소중에서 다시 순서대로 택한다. 이 과정을 k 번 반복하면 하나의 순열이 만들어진다. 만들어진 순열을 yield 하고 다시 앞 단계로 돌아가서 앞에서 선택했던 원소의 다음 원소를 고른다.
말로 쓰니까 좀 장황하고 길어지는 감이 있는데, 코드를 보면 매우 간단하다.
def perms_dups(ns, /, k=None):
def helper(prefix, ws, k):
if k == 0:
yield prefix
return
for i, w in enumerate(ws):
yield from helper((*prefix, w), (*ws[:i], *ws[i+1:]), k-1)
yield from helper([], ys, len(ns) if k is None else k)매 단계에서 순서대로 원소를 하나 고르고, 고른 것을 prefix 뒤에 붙인다. 그리고 고른 원소를 뺀 나머지 값들과 함께 재귀적으로 yield from 구문으로 넘겨주는 것이다. 이렇게 하면 itertools.permutations() 함수와 완전히 동일하게 작동한다.
중복 순열 생성하기
중복 순열 생성은 바로 위 순열 생성 함수와 똑같은 로직이다. 다만 한 단계에서 원소를 하나를 골랐을 때, 목록에서 고른 원소를 빼지 않으면 된다.
def perms_dups(ns, /, k=None):
def helper(prefix, ws, k):
if k == 0:
yield prefix
return
for i, w in enumerate(ws):
yield from helper((*prefix, w), ws, k-1)
yield from helper([], ys, len(ns) if k is None else k)
itertools.products() 를 사용해서 중복순열을 만드는 방법은 아래와 같다. product()가 연속열의 리스트를 인자로 받는게 아니라, 조합할 인자들을 각각 인자로 받기 때문이다.
from itertools import product
ns = [1,2,3]
k = 3
for p in product(*([ns] * k)):
print(p)조합 제너레이터
알파벳에서 3글자를 뽑아 조합을 만들 때, “ABC”, “BAC” 는 순열에서는 서로 다른 것이지만, 조합에서는 뽑는 순서를 신경쓰지 않으므로 같은 것으로 본다. 따라서 조합을 만들 때에는 앞부분에서 사용했던 원소를 뒤에서 계속 사용하지 않으면 된다.
def combs(ns, /, k=None):
def helper(prefix, ws, k):
if k == 0:
yield prefix
return
for i, w in enumerate(ws):
yield from helper((*prefix, w), ys[i+1:], k-1)
yield from helper([], ys, len(ns) if k is None else k)
중복 조합 제너레이터
중복 조합의 경우에는 앞에서 사용했던 원소를 제외하는 과정에서 방금 고른 원소를 제거하지 않고 그대로 두면 된다.
def combs(ns, /, k=None):
def helper(prefix, ws, k):
if k == 0:
yield prefix
return
for i, w in enumerate(ws):
yield from helper((*prefix, w), ys[i:], k-1)
yield from helper([], ys, len(ns) if k is None else k)
중복된 원소를 포함하는 순열 만들기
순열, 조합을 구하는 것과는 별개로 원소중에서 각각의 원소가 m개, n개 씩 있는 경우의 순열은 약간 다른 방식으로 구현된다. 각 원소마다 사용할 수 있는 횟수가 다르기 때문에, 사용 가능한 원소의 개수를 추적하는 것이 필요하다. 자세한 설명과 그에 대한 코드는 아래 글을 참고하기 바란다.