파이썬 itertools에서 Combinatoric iterators사용하기

itertools 에서 Combinatoric iterators

 

이번에는 조합 및 순열 문제를 쉽게 풀기 위한 itertools에서 Combinatoric iterators에 대해 알아 보겠습니다.

 

먼저 itertools란 PAL, Haskell 및 SML의 구성에서 영감을 얻은 여러가지 number of iterator building blocks를 구현합니다. 각각은 파이썬에서 적합한 형태로 개편되었습니다.

 

이 모듈을 자체적으로 또는 조합하여 유용한 빠르고 메모리 효율적인 도구의 핵심 세트를 표준화 합니다. 이들은 함께 "iterator algebra"를 형성하여 순수 Python에서 간결하고 효율적으로 특수 도구를 구성할 수 있습니다.

 

저는 여기에서 순열과 조합을 지원하는 Combinatoric iteratos에 대해 알아보겠습니다.

 

먼저 iterator은 다음과 같습니다.

 

combiatoric iterators

Iterator	Arguments	Result
product( )	p,q, ...[repeat=1]	cartesian product, equivalent to a nested for-loop
permutations( )	p[,r]	r-length tuples, all possible orderings, no repeated elements
combinations( )	p,r	r-length tuples, in sorted order, no repeated elements
combinations_with_replacement()	p,r	r-length tuples, in sorted order, with repeated elements

다음은 사용 예제를 설명하겠습니다.

Product

 

product는 중복순열을 의미합니다. 예를 들면 (1,2,3)이라는 숫자가 있는데 2개를 뽑아 숫자 순열을 만들면 다음과 같이 표현할 수 있습니다. (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)

이것을 파이썬으로 나타내겠습니다.

 

먼저 Product를 사용 하기위해 다음과 같이 import 하겠습니다. product는 별도의 설치 없이 간단하게 import하여 사용할 수 있습니다. product는 다른 iterator들과는 다르게 repeat이라는 표현을 사용합니다.

 

from itertools import product
lst = [1,2,3]
pro_list = list(product(lst,repeat=2))
print(pro_list)
## 출력 값 
# [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

 

Permutations

 

Permutations은 순열을 의미 합니다. 예를 들면 (1,2,3)이라는 숫자가 있는데 2개를 뽑아 숫자 순열을 만들면 다음과 같이 표현할 수 있습니다. (1,2),(1,3),(2,1),(2,3),(3,1),(3,2)

이것을 파이썬으로 나타내겠습니다.

 

from itertools import permutations
lst = [1,2,3]
permu_list = list(permutations(lst,2))
print(permu_list)
## 출력 값
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

Combinations

 

Combinations는 조합을 의미합니다. 예를 들면 (1,2,3)이라는 숫자가 있는데 2개를 뽑아 조합을 만들면 다음과 같이 표현할 수 있습니다. (1,2),(1,3),(2,3)

이것을 파이썬으로 나타내겠습니다.

 

from itertools import combinations
lst = [1,2,3]
combi_lst = list(combinations(lst,2))
print(combi_lst)
## 출력 값
# [(1, 2), (1, 3), (2, 3)]

 

Combinations_with_replacement

 

Combinations_with_replacement는 중복 조합을 의미합니다. 예를 들면(1,2,3)이라는 숫자가 있는데 2개를 뽑아 조합을 만들면 다음과 같이 표현할 수 있습니다. (1,1),(1,2),(1,3),(2,2),(2,3),(3,3)

이것을 파이썬으로 나타내겠습니다. iterator의 이름이 너무 길어서 combi라고 별칭을 지어줬습니다.

from itertools import combinations_with_replacement as combi
lst = [1,2,3]
combi_list = list(combi(lst,2))
print(combi_list)
## 출력 값
# [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

 

여기 있는 것들을 이용하면 백준에서 다음과 같은 문제를 쉽게 풀 수 있습니다.

 

백준 문제 list

 

https://www.acmicpc.net/workbook/view/2052 에들어가서 N과 M 문제를 다 푸시면 itertools를 사용하는데 익숙해 질 것입니다.