특정한 원소를 가지고 만들 수 있는 모든 순열/조합을 생성하려는 경우, 기본적으로는 itertools 모듈을 사용한다. combinations()
는 생성 가능한 모든 조합을 만드는 제너레이터 함수이며, permutations()
는 생성 가능한 모든 순열을 만들어내는 제너레이터이다. 중복 조합의 경우에는 combinations_with_replacement()
라는 다소 장황한 이름의 제너레이터가 있다. 중복 순열이 조금 애매한데, 중복 순열은 원래 원소의 집합에 대한 N번의 데카르트 곱으로 만들어진다. 그래서 product()
함수를 사용해서 약간 돌려서(?) 이용한다.
오늘은 순열, 조합, 중복조합, 중복순열을 각각 생성하는 제너레이터를 직접 구현하는 방법을 소개하겠다. 실제로 기본적인 아이디어는 동일한데, 파이썬에서 제너레이터를 재귀적으로 사용할 수 있게 해주는 yield from
문법을 사용하기 때문에 구현도 매우 간단하고 성능도 좋은 편이다. 재귀 깊이에 대한 제한은 동일하게 적용되지만, 대신 매번 순열/조합을 생성하는 방식이기 때문에 메모리 스루풋도 나쁘지 않은 편이다.
더 보기 »순열 조합 제너레이터 구현하기