콘텐츠로 건너뛰기
Home » 조합

조합

순열과 조합 – itertools (python)

알려져 있는 원소들로 구성되는 가능한 모드 조합 및 순열을 구하려 할 때, 이를 직접 구현해보는 것도 좋지만 itertools 모듈에 있는 함수를 사용하는 것을 추천한다. 이 함수들은 기본적으로 제너레이터 함수이기 때문에 한번에 리스트 등으로 만들기 전까지는 메모리에 큰 부담을 주지 않으며 성능도 적절한 편이다. 오늘은 itertools의 함수 중에서 순열과 조합에 관련된 함수들을 알아보도록 하자.

더 보기 »순열과 조합 – itertools (python)

순열 조합 제너레이터 구현하기

특정한 원소를 가지고 만들 수 있는 모든 순열/조합을 생성하려는 경우, 기본적으로는 itertools 모듈을 사용한다. combinations() 는 생성 가능한 모든 조합을 만드는 제너레이터 함수이며, permutations() 는 생성 가능한 모든 순열을 만들어내는 제너레이터이다. 중복 조합의 경우에는 combinations_with_replacement() 라는 다소 장황한 이름의 제너레이터가 있다. 중복 순열이 조금 애매한데, 중복 순열은 원래 원소의 집합에 대한 N번의 데카르트 곱으로 만들어진다. 그래서 product() 함수를 사용해서 약간 돌려서(?) 이용한다.

오늘은 순열, 조합, 중복조합, 중복순열을 각각 생성하는 제너레이터를 직접 구현하는 방법을 소개하겠다. 실제로 기본적인 아이디어는 동일한데, 파이썬에서 제너레이터를 재귀적으로 사용할 수 있게 해주는 yield from 문법을 사용하기 때문에 구현도 매우 간단하고 성능도 좋은 편이다. 재귀 깊이에 대한 제한은 동일하게 적용되지만, 대신 매번 순열/조합을 생성하는 방식이기 때문에 메모리 스루풋도 나쁘지 않은 편이다.

더 보기 »순열 조합 제너레이터 구현하기