알려져 있는 원소들로 구성되는 가능한 모드 조합 및 순열을 구하려 할 때, 이를 직접 구현해보는 것도 좋지만 itertools 모듈에 있는 함수를 사용하는 것을 추천한다. 이 함수들은 기본적으로 제너레이터 함수이기 때문에 한번에 리스트 등으로 만들기 전까지는 메모리에 큰 부담을 주지 않으며 성능도 적절한 편이다. 오늘은 itertools의 함수 중에서 순열과 조합에 관련된 함수들을 알아보도록 하자.
오일러 프로젝트 41 번은 n자리 소수이면서 1-n 팬디지털 소수인 것들 중에서 가장 큰 소수를 찾는다. 이는 의외로 매우 쉽게 찾을 수 있다. 더 보기 »오일러 프로젝트 41
순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다.
def rec_perm(iterable):
if len(iterable) == 1:
return [list(iterable)]
result = []
for i in range(len(iterable)):
head = iterable[i]
tail = iterable[:i] + iterable[i+1:]
result += [[head] + x for x in rec_perm(tail)]
return result
이 알고리듬의 가장 큰 문제는 한 번에 모든 순열을 다 생성해서 그 리스트를 만환한다는 말이다. 만약 원소가 100개라면?1 메모리 부족으로 컴퓨터가 뻗을 수 있다. 물론 10개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다. 더 보기 »순열생성로직연구
특정한 원소를 가지고 만들 수 있는 모든 순열/조합을 생성하려는 경우, 기본적으로는 itertools 모듈을 사용한다. combinations() 는 생성 가능한 모든 조합을 만드는 제너레이터 함수이며, permutations() 는 생성 가능한 모든 순열을 만들어내는 제너레이터이다. 중복 조합의 경우에는 combinations_with_replacement() 라는 다소 장황한 이름의 제너레이터가 있다. 중복 순열이 조금 애매한데, 중복 순열은 원래 원소의 집합에 대한 N번의 데카르트 곱으로 만들어진다. 그래서 product() 함수를 사용해서 약간 돌려서(?) 이용한다.
오늘은 순열, 조합, 중복조합, 중복순열을 각각 생성하는 제너레이터를 직접 구현하는 방법을 소개하겠다. 실제로 기본적인 아이디어는 동일한데, 파이썬에서 제너레이터를 재귀적으로 사용할 수 있게 해주는 yield from 문법을 사용하기 때문에 구현도 매우 간단하고 성능도 좋은 편이다. 재귀 깊이에 대한 제한은 동일하게 적용되지만, 대신 매번 순열/조합을 생성하는 방식이기 때문에 메모리 스루풋도 나쁘지 않은 편이다.