Site icon Wireframe

순열과 조합 – itertools (python)

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

순열

함수 permutations() 는 주어진 반복가능 객체의 각 요소로부터 순열을 생성하는 제너레이터를 리턴한다. 두 번째 인자로 각 순열의 크기를 지정하는 것도 가능하다.

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 모듈에서는 같은 것을 포함하는 순열을 생성해주는 함수는 제공하지 않지만, 아래 포스팅에서 이 순열을 구하는 코드를 소개하고 있으니 참고하면 되겠다.

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

블로그에 순열, 조합, 중복순열, 중복조합을 생성하는 제너레이터를 직접 구현하는 방법을 설명한 아래 글도 관심이 있다면 읽어보는 것도 좋겠다.

Exit mobile version