[Python] 순열 / 조합 제너레이터

새해 복 많이 받으세요

순열/조합 알고리듬 관련해서 검색해보면 거의 대부분의 블로그의 글이 재귀 호출을 통한 구현에 대해 쓰고 있다. 뭐 n개 원소를 가진 집합에 대해서 최대 n회의 깊이를 가지는 재귀라서 안전하긴 하지만… 다만 재귀로 작성하는 경우 yield 구문을 쓸 수 없기 때문에 순열을 찍어보는 거 말고 실제로 구해야 하는 경우라면 스택의 크기와 상관없이 메모리가 문제가 된다. 당장 알파벳 26개로 만들 수 있는 순열의 수만해도 ‘403291461126605635584000000’개가 된다. 따라서 가능하면 재귀를 사용하지 않고, 순열을 매회 계산할 수 있는 로직이 있다면 좋을 것이다.

기본적인 아이디어는 표본 집합을 얼려놓고, 대신 각 원소의 인덱스를 갖는 리스트를 조작하면서 매 순열을 계산하는 것이다.

def combinations(iterable, r):
# combinations('ABCD', 2) -> AB AC AD BC BD CD
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j1] + 1
yield tuple(pool[i] for i in indices)
def combinations2(iterable, r):
pool = tuple(iterable)
n = len(pool)
for indices in permutations(range(n), r):
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)

view raw
Combinations.py
hosted with ❤ by GitHub

# 순열을 구하는 함수
# 재귀를 사용하지 않고
# 제너레이터를 리턴함.
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, nr, 1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n i
else:
j = cycles[i]
indices[i], indices[j] = indices[j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
# 데카르트 곱을 이용하는 방법
# product 함수는 주어진 연속열의 데카르트 곱을 생성한다.
def product(*args, **kwgs):
pools = map(tuple, args) * kwgs.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
# 데카르트 곱을 사용하여 r 개의 원소를 취했을 때
# 이를 출력하면 사전식 순열이 된다.
def permutations2(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)

view raw
Permutations.py
hosted with ❤ by GitHub