알려져 있는 원소들로 구성되는 가능한 모드 조합 및 순열을 구하려 할 때, 이를 직접 구현해보는 것도 좋지만 itertools 모듈에 있는 함수를 사용하는 것을 추천한다. 이 함수들은 기본적으로 제너레이터 함수이기 때문에 한번에 리스트 등으로 만들기 전까지는 메모리에 큰 부담을 주지 않으며 성능도 적절한 편이다. 오늘은 itertools의 함수 중에서 순열과 조합에 관련된 함수들을 알아보도록 하자.
순열
함수 permutations() 는 주어진 반복가능 객체의 각 요소로부터 순열을 생성하는 제너레이터를 리턴한다. 두 번째 인자로 각 순열의 크기15개 중 3개를 골라 만드는 순열을 만들 때 유용하다.를 지정하는 것도 가능하다.
list(permutations(range(3))
# 3! => 6 results
# (0, 1, 2)
# (0, 2, 1)
# (1, 0, 2)
# (1, 2, 0)
# (2, 0, 1)
# (2, 1, 0)조합
조합은 골라낸 요소들 간의 순서를 고려하지 않는 목록이다. 순열에서 (0, 1, 2), (1, 0, 2), (2, 1, 0) 은 모두 다른 항목이지만, 조합에서는 같은 것으로 본다. 따라서 5개에서 3개를 뽑는 경우의 순열은 5 * 4 * 3 = 60가지 이지만, 조합의 경우는 60 / ( 3 * 2 * 1) = 10 가지만 존재한다.
print('\n'.join(f'# {x}' for x in combinations(range(5), 3)))
# (0, 1, 2)
# (0, 1, 3)
# (0, 1, 4)
# (0, 2, 3)
# (0, 2, 4)
# (0, 3, 4)
# (1, 2, 3)
# (1, 2, 4)
# (1, 3, 4)
# (2, 3, 4)중복 조합
중복 조합은 N개의 원소에서 R개를 고를 때 중복을 허용하는 조합의 경우를 만들어준다.
print('\n'.join(f'# {x}' for x in combinations_with_replacement(range(3), 3)))
# (0, 0, 0)
# (0, 0, 1)
# (0, 0, 2)
# (0, 1, 1)
# (0, 1, 2)
# (0, 2, 2)
# (1, 1, 1)
# (1, 1, 2)
# (1, 2, 2)
# (2, 2, 2)중복 순열
itertools 모듈에는 N개의 요소 중에서 R개를 뽑는 중복 순열을 생성하는 명시적인 함수는 존재하지 않는다. 대신에 product(*iterables) 함수를 사용해서 이를 구현하는 것이 가능하다. product() 함수는 주어진 연속열들의 데카르트 곱을 생성하는 함수로, 길이 N인 연속열을 R번 반복하여 중복 순열과 같은 효과를 얻을 수 있다. 다음 예는 (0, 1, 2) 중에서 중복을 허용하여 2개를 고르는 모든 순열을 출력하는 예이다.
print(list(
product(*(range(3) for _ in range(2)))
))
# [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]같은 것을 포함하는 순열
순열, 조합 문제의 특별한 케이스 중에는 같은 것을 포함하는 순열이 있다. (a, a, a, b, b)를 가지고 만들 수 있는 모든 순열의 경우를 찾는 문제가 여기에 해당하며, 이는 중복 순열과는 다르다. 아쉽게도 itertools 모듈에서는 같은 것을 포함하는 순열을 생성해주는 함수는 제공하지 않지만, 아래 포스팅에서 이 순열을 구하는 코드를 소개하고 있으니 참고하면 되겠다.
순열 조합 제너레이터를 직접 구현하기
블로그에 순열, 조합, 중복순열, 중복조합을 생성하는 제너레이터를 직접 구현하는 방법을 설명한 아래 글도 관심이 있다면 읽어보는 것도 좋겠다.