[파이썬] itertools, 완전탐색을 공부합시다.

완전탐색이란?

문제에서 주어질 수 있는 모든 경우의 수를 탐색하는 알고리즘을 말합니다.

 

 

 

이번 글에서는 알고리즘에서 주로 쓰는 조합형 완탐 함수 4가지를 소개합니다.

 

• product
• permutations
• combinations
• combinations_with_replacement

 

조합형 :

 

product, 곱집합

대표적인 이름으로는 곱집합, 데카르트의 곱이라고 합니다.

곱집합은 for문 두개를 섞어놨다고 생각하시면 됩니다.

 

product(p, q, … [repeat=1]) 이런 형태로 사용할 수 있습니다.

 

예시

itertools.product('1234', '1234') 또는
itertools.product('1234', repeat=2)

[('1', '1'), ('1', '2'), ('1', '3'), ('1', '4'), 
 ('2', '1'), ('2', '2'), ('2', '3'), ('2', '4'), 
 ('3', '1'), ('3', '2'), ('3', '3'), ('3', '4'), 
 ('4', '1'), ('4', '2'), ('4', '3'), ('4', '4')]

 

 

 

permutations, 순열

반복 가능한 요소의 연속된 길이가 r인 순열을 반환합니다.

r이 지정되지 않았거나 None이라면, r의 기본값으로 반복가능한 수열의 길이가 적용됩니다. 가능한 모든 최대 길이의 순열이 생성됩니다.

 

가능한 모든 순서를 반환하며, 반복되는 요소가 없다는 특징이 있습니다.

 

permutations(p[, r]) 이런 형태로 사용 할 수 있습니다.

 

예시

itertools.permutations('1234', 2)

[('1', '2'), ('1', '3'), ('1', '4'),
 ('2', '1'), ('2', '3'), ('2', '4'),
 ('3', '1'), ('3', '2'), ('3', '4'), 
 ('4', '1'), ('4', '2'), ('4', '3')]

 

 

 

combinations, 조합

반복 가능한 요소의 길이 r의 서브 시퀀스들을 반환합니다.

 

combinations(p, r) 이런 형태로 사용할 수 있습니다.

 

조합이기 때문에, 반복되는 요소가 없는 정렬된 순서들을 반환합니다.

 

예시

combinations('1234', 2)

[('1', '2'), ('1', '3'), ('1', '4'),
 ('2', '3'), ('2', '4'), 
 ('3', '4')]

 

 

 

combinations_with_replacement, 중복이 가능한 조합

반복 가능한 요소의 길이 r의 서브 시퀀스들을 반환하는데, 개별 요소가 두번 이상 반복할 수 있습니다.

 

combinations_with_replacement(p, r) 이런 형태로 사용할 수 있습니다.

 

조합에서 개별 요소마다 두번 이상 반복할 수 있습니다.

 

예시

combinations_with_replacement('1234', 2)

[('1', '1'), ('1', '2'), ('1', '3'), ('1', '4'),
 ('2', '2'), ('2', '3'), ('2', '4'), 
 ('3', '3'), ('3', '4'), 
 ('4', '4')]