[Python] 순열과 조합 (combinations, permutations)

📌Itertools

 코딩테스트 알고리즘 문제를 풀다보면 조합과 순열의 개념이 자주 등장하게 된다. 파이썬의 itertools 패키지를 사용하여 순열, 조합, product를 쉽게 구현할 수 있다. itertools는 combinations, permutations, product 세 메소드를 통해 지원하고 있다. 이때 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환된다. 

 

 itertools에서 사용되는 메소드는 모두 generator이기 때문에 list()로 캐스팅하여 다른 곳에 저장해두지 않으면 한 번의 루핑 이후 사라지게 된다는 점에 유의해야 한다.(실행한 결과를 사용하기 위해서는 list로 변환하여 저장하자) 

#중복 없는 조합
from itertools import combinations
#중복 있는 조합
from itertools import combinations_with_replacement as com
#중복 없는 순열 
from itertools import permutaitons
#중복 있는 순열 / 각 집단에서 추출
from itertools import product

📌Combinations

조합은 서로 다른 n개의 원소를 가지는 집합에서 r(0<r<=n)개를 중복 없이, 순서를 고려하지 않고 선택하는 것을 의미한다. 

combinations()는 한 리스트(iterable)에서 r개의 원소를 중복없이 뽑을 수 있다.

사용하는 방식은 아래와 같다. 

from itertools import cominations

combinations(iterable, r)

 

📌Combinations With Replacement 

중복 조합은 서로 다른 n개의 원소를 가지는 집합에서 r(0<r<=n)개를 중복이 있고, 순서를 고려하지 않고선택하는 것을 의미한다. 

순서 없이 뽑는 것은 조합과 동일하지만, 이미 뽑은 것을 또 뽑을 수 있는 중복이 가능하다는 차이점이 있다. 

from itertools import combinations_with_replacement 

combinations_with_replacement(iterable, r)

 

📌Permutations 

순열은 서로 다른 n개의 원소를 가지는 집합에서 r(0<r<=n)개를 중복 없이, 순서에 상관있게 선택하는 것을 의미한다. 

permutations()는 한 리스트(iterable)에서 r개의 원소를 중복없이, 순서대로 뽑을 수 있다. 

사용하는 방식은 아래와 같다.

from itertools import permutations

permutations(iterable, r)

 

 

📌Product

product는 여러 iterable의 데카르트 곱을 반환한다. 

product는 다른 함수와 달리 인자로 여러 iterable을 넣어줄 수 있고, 그 원소들 간의 모든 짝을 반환하게 된다. 

from itertools import product

product(*iterable, repeat=n)
product(iterable1, iterable2, repeat=n)

 

예시는 다음과 같다.

lst = ['012','abc','ABC']
pd = list(product(*lst))
#pd = list(product(lst,repeat=3))과 같은 코드 
#[('0','a','A'),('0','a','B'),('0','a','C'), ('1','a','A) ......