알려져 있는 원소들로 구성되는 가능한 모드 조합 및 순열을 구하려 할 때, 이를 직접 구현해보는 것도 좋지만 itertools 모듈에 있는 함수를 사용하는 것을 추천한다. 이 함수들은 기본적으로 제너레이터 함수이기 때문에 한번에 리스트 등으로 만들기 전까지는 메모리에 큰 부담을 주지 않으며 성능도 적절한 편이다. 오늘은 itertools의 함수 중에서 순열과 조합에 관련된 함수들을 알아보도록 하자.
주어진 원소로 가능한 순열/조합을 생성하는 기능은 표준 라이브러리 내 itertools 모듈을 통해 사용할 수 있다. (참고로 단순히 순열 조합을 생성하는 방법은 의외로 간단해서 직접 구현해서 사용해도 된다.) 그런데 가끔 볼 수 있는 문제 중에는 같은 원소가 여러 개 있을 때의 순열을 구하는 문제가 있다. 이 문제는 한 개씩 있는 원소를 중복해서 순열/조합을 만드는 중복순열, 중복조합과는 달리 사용가능한 원소가 중복은 되지만 그 개수에 제한이 있다는 것이다. 흔히 “같은 것을 포함하는 순열”이라고 하던데, 오늘은 이처럼 같은 원소를 여러 개 포함하는 순열을 만드는 방법에 대해서 알아보자.
더 보기 »같은 것을 포함하는 순열 생성기오일러 프로젝트 41 번은 n자리 소수이면서 1-n 팬디지털 소수인 것들 중에서 가장 큰 소수를 찾는다. 이는 의외로 매우 쉽게 찾을 수 있다. 더 보기 »오일러 프로젝트 41
오일러 프로젝트 24 번은 숫자 10개(0~9)로 만들어지는 순열 중에서 백만번째 항을 구하는 문제이다. 어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다. 이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다. 012, 021, 102, 120, 201, 210… 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로… 더 보기 »오일러 프로젝트 24
오일러 프로젝트 15 번 문제는 간단한 경우의 수 문제이다.
더 보기 »오일러 프로젝트 15
특정한 원소를 가지고 만들 수 있는 모든 순열/조합을 생성하려는 경우, 기본적으로는 itertools 모듈을 사용한다. combinations() 는 생성 가능한 모든 조합을 만드는 제너레이터 함수이며, permutations() 는 생성 가능한 모든 순열을 만들어내는 제너레이터이다. 중복 조합의 경우에는 combinations_with_replacement() 라는 다소 장황한 이름의 제너레이터가 있다. 중복 순열이 조금 애매한데, 중복 순열은 원래 원소의 집합에 대한 N번의 데카르트 곱으로 만들어진다. 그래서 product() 함수를 사용해서 약간 돌려서(?) 이용한다.
오늘은 순열, 조합, 중복조합, 중복순열을 각각 생성하는 제너레이터를 직접 구현하는 방법을 소개하겠다. 실제로 기본적인 아이디어는 동일한데, 파이썬에서 제너레이터를 재귀적으로 사용할 수 있게 해주는 yield from 문법을 사용하기 때문에 구현도 매우 간단하고 성능도 좋은 편이다. 재귀 깊이에 대한 제한은 동일하게 적용되지만, 대신 매번 순열/조합을 생성하는 방식이기 때문에 메모리 스루풋도 나쁘지 않은 편이다.