새해 복 많이 받으세요
순열/조합 알고리듬 관련해서 검색해보면 거의 대부분의 블로그의 글이 재귀 호출을 통한 구현에 대해 쓰고 있다. 뭐 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[j–1] + 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) |
| # 순열을 구하는 함수 | |
| # 재귀를 사용하지 않고 | |
| # 제너레이터를 리턴함. | |
| 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, n–r, –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) |