[Python] itertools - 순열, 조합, 중복순열, 중복조합

코딩테스트 '완전탐색' 문제를 풀다보면 순열, 조합을 사용해서 풀 때가 종종 있다.

순열, 조합은 파이썬의 itertools 라이브러리를 불러와 사용할 수 있고 몇 가지 메소드를 사용해 쉽게 구현할 수 있다.

파이썬 공식문서에는 다양한 종류의 itertools 함수가 존재하는데 오늘은 순열, 조합, 중복순열, 중복조합에 대해서 정리하려고 한다.

 

조합형 iterator에는 다음 4가지가 있다.

iterator	이름	필요한 인자	출력 결과
product()	중복순열	(p, q, r, ...,  repeat = n)	모든 데이터를 전부 결합한 결과(=Cartesian  Product)
permutations()	순열	(p,r)	r길이의 튜플들, 순서 고려, 반복 요소 없음
combinations()	조합	(p, r)	r길이의 튜플들, 순서 고려하지 않음, 반복 요소 없음
combinations_with_replacement()	중복조합	(p, r)	r길이의 튜플들, 순서 고려하지 않음, 반복요소 있음

 

1. Product()

• generator 표현식에서 중첩된 for-루프와 동일하다.
• repeat 키워드 인자를 사용해서 반복 횟수를 지정한다.

product(A, repeat=4)
>> product(A, A, A, A) 와 같은 것

from itertools import product

# repeat 인자를 사용했을 때
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)


# repeat 인자 없이
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(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)

 

 

2. Permutations()

• 요소의 연속된 길이 r 순열을 반환한다.
• 순서의 의미가 있다. (AB 와 BA는 다른 것으로 취급한다.)

from itertools import permutations

for i in permutations([1, 2, 3, 4], 2):
	print(i, end = '')

>> (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

 

3. Combinations()

• 요소의 연속된 길이 r 순열을 반환한다.
• 순서의 의미가 없다. (AB 와 BA는 같은 것으로 취급한다.)

from itertools import combinations

for i in combinations([1,2,3,4], 2):
	print(i, end = ' ')

>> (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

 

 

4. Combinations_with_replacement()

• 중복 조합
• 길이 r 서브 시퀀스를 반환하는데, 개별 요소를 두 번 이상 반복할 수 있다.

from itertools import combinations_with_replacement

for i in combinations_with_replacement([1,2,3,4], 2):
	print(i, end = ' ')
    
>> (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

 

 

실수하기 쉬운 것

• 순열, 조합, 중복순열, 중복조합 객체를 그대로 출력하면 원소를 얻을 수 없다.
• for 문을 통해서 원소를 하나씩 얻을 수 있다.

from itertools import combinations

a = [1,2,3,4,5]

combs = combinations(a, 2)

print(combs)

>> <itertools.combinations object at 0x7f7ee0d5fe00>

 

 

References

• https://docs.python.org/ko/3/library/itertools.html#itertools.product

itertools — Functions creating iterators for efficient looping

• https://juhee-maeng.tistory.com/91