새해 복 많이 받으세요
순열/조합 알고리듬 관련해서 검색해보면 거의 대부분의 블로그의 글이 재귀 호출을 통한 구현에 대해 쓰고 있다. 뭐 n개 원소를 가진 집합에 대해서 최대 n회의 깊이를 가지는 재귀라서 안전하긴 하지만… 다만 재귀로 작성하는 경우 yield 구문을 쓸 수 없기 때문에 순열을 찍어보는 거 말고 실제로 구해야 하는 경우라면 스택의 크기와 상관없이 메모리가 문제가 된다. 당장 알파벳 26개로 만들 수 있는 순열의 수만해도 ‘403291461126605635584000000’개가 된다. 따라서 가능하면 재귀를 사용하지 않고, 순열을 매회 계산할 수 있는 로직이 있다면 좋을 것이다.
기본적인 아이디어는 표본 집합을 얼려놓고, 대신 각 원소의 인덱스를 갖는 리스트를 조작하면서 매 순열을 계산하는 것이다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 순열을 구하는 함수 | |
| # 재귀를 사용하지 않고 | |
| # 제너레이터를 리턴함. | |
| 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) |