Python 순열, 조합, 곱집합, 중복 순열, 중복 조합 튜토리얼

파이썬으로 코딩테스트를 준비하다보면 가장 큰 장점이 표준 라이브러리입니다. 굳이 구현할 필요 없이 파이썬에서 만들어져있는 라이브러리를 사용하여 쉽게 알고리즘을 짤 수 있습니다. 이번에는 그 대표적인 예로 itertools를 사용하여 순열, 조합, product를 구현해보았습니다.

사용 전에 주의사항 : combinations, permutations, product 세 메소드 모두 generator이기 때문에 list()로 캐스팅하여 다른 곳에 저장 해두지 않으면 한 번의 루핑 이후 사라지게 됩니다.

파이썬 레퍼런스 : https://docs.python.org/ko/3/library/itertools.html

📌 Itertools

파이썬에 내장된 itertools 패키지의 combinations 모듈과 permutations 모듈을 통해 쉽게 순열과 조합을 구할 수 있습니다. 이 떄 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환됩니다.

📌 combinations

조합을 표현할 때 사용되는 메소드입니다. 즉, 한 리스트에서 중복을 허용하지 않고 모든 경우의 수를 구하는 것입니다.

• 조합 : 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑는 모든 경우의 수

• 시간복잡도 : n! / r! / (n - r)!

combinations(반복 가능한 객체, r)

from itertools import combinations

_list = [1, 2, 3]
combi = list(combinations(_list, 2))
print(combi)														
# [(1, 2), (1, 3), (2, 3)]
# 갯수 별로 조합을 반복할 수 있다.
for i in range(1, len(_list) + 1):
    print(list(combinations(_list, i)))
# [(1,), (2,), (3,)]
# [(1, 2), (1, 3), (2, 3)]
# [(1, 2, 3)]

📌 permutations

순열을 표현할 때 사용되는 메소드입니다. 한 리스트에서 중복을 허용하고 모든 경우의 수를 구하는 것입니다.

• 순열 : 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열하는 모든 경우의 수
• 시간 복잡도 : n! / r!

permutations(반복 가능한 객체, r)

from itertools import permutations

_list = [1, 2, 3]
perm = list(permutations(_list, 2))
print(perm)	

📌 product

데카르트 곱이라고도 하는 cartesian product를 표현할 때 사용하는 메소드입니다. 이 메소드의 특징은 두 개 이상의 리스트(문자열)의 모든 조합을 구할 때 사용됩니다.

아래의 예시에서는 _list 내에 있는 세 개의 문자열에 대한 곱집합을 구하는 과정입니다.

from itertools import product

_list = ["012", "abc", "!@#"]
pd = list(product(*_list))
# [('0', 'a', '!'), ('0', 'a', '@'), ('0', 'b', '!'), ('0', 'b', '@'), ('1', 'a', '!'), ('1', 'a', '@'), ('1', 'b', '!'), ('1', 'b', '@')]

📌 중복 순열

중복 순열과 위의 product가 처음에는 다른 건 줄 알았는데 개념적으로 보면 동일합니다. 다만 여러 사용법이 있어서 따로 정리를 하였습니다.

• product(반복 가능한 객체, repeat=1)

from itertools import product

for i in product([1,2,3],'ab'):
    print(i, end=" ")
# (1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b')

for i in product([1,2,3], repeat=2):
    print(i, end=" ")
# (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)

for i in product(range(3), range(3), range(3)):
    print(i, end=" ")
# (0, 0, 0) (0, 0, 1) (0, 0, 2) (0, 1, 0) (0, 1, 1) (0, 1, 2) (0, 2, 0) (0, 2, 1) (0, 2, 2) (1, 0, 0) (1, 0, 1) (1, 0, 2) (1, 1, 0) (1, 1, 1) (1, 1, 2) (1, 2, 0) (1, 2, 1) (1, 2, 2) (2, 0, 0) (2, 0, 1) (2, 0, 2) (2, 1, 0) (2, 1, 1) (2, 1, 2) (2, 2, 0) (2, 2, 1) (2, 2, 2)

📌 중복 조합

• combinations_with_replacement(반복 가능한 객체, r)

from itertools import combinations_with_replacement

for cwr in combinations_with_replacement([1,2,3,4], 2):
    print(cwr, end=" ")
# (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

실제로 이러한 순열, 조합 등을 직접 구현하면 코드 길이와 시간만 더 길어지기 때문에 이러한 라이브러리를 사용하는 것이 더 효율적이라고 합니다. 다음에는 이 라이브러리를 응용해서 코딩 테스트 문제를 풀어 후기를 남기도록 하겠습니다 !