파이썬으로 Combinations 구현하기 - Recursion

이번 포스팅에서는 순열과 조합중, 조합 함수를 직접 구현을 함께 해보겠습니다.
사실 파이썬 기본 라이브러리중 itertools 모듈에는 combinations, permutations함수가 이미 정의 되어 있습니다.
이를 단순히 사용하기만 하는 것은 어렵지 않습니다. 하지만 순열과 조합의 정의, 우리가 어떠한 모집단에서
표본을 추출하는 과정을 생각해보면 가능한 모든 표본의 가능성을 코드로 쉽게 구현할 수 있습니다.

이번에는 간단하게 조합함수(combination)를 함께 구현해보겠습니다.

 

---

조합(Combination)이란 무엇인가요?

조합의 정의를 함께 살펴볼까요? 대학 이전에서의 표기법은 nCk 로 주로 표현합니다.
또 대학 이후에서는 주로 아래의 이미지와 같이 표기됩니다.

모두 읽을 때에는 n combination k로 읽으면 되겠습니다.

수학에서 말하는 조합은 아래와 같습니다.
"서로 다른 n개중, k개를 선택할 때 그 선택된 k개의 표본의 가능한 모든 결과의 수" 입니다.
하나 조심할 것은 순열과 다르게 조합의 경우, 그 조합은 순서는 고려할 필요 없다는 것입니다.

 

하지만 우리가 원하는 것은 그 가능한 결과의 가지수가 아닙니다. 우리가 원하는 것은 가능한 모든 결과 그 자체입니다.

그렇다면 어떻게 하면 그 모든 가능성을 구할 수 있을까요? Explicit하게 구할 수도 있겠지만, 문제를 그 보다 더 작은 부분문제(subproblem)으로써 나누고 해결해 보는 것도 좋을 것 같습니다. 바로 아래에서 그 문제해결의 실마리를 찾아보겠습니다.

 

추출의 과정

우리가 추출을 하면 보통 어떻게 할까요? 쉬운 예를 들어봅시다.
1부터 5의 숫자가 붙은 같은 크기, 무게, 성분의 동전 다섯 개가 있다고 생각해봅시다. 이 중에서 3개를 고르는 상황을 생각해보겠습니다. 정의에 따르면 이 중에서 3개를 추출을 하면 되겠죠. 그래서 한 번에 3개를 추출할 수도 있을 겁니다.
하지만 위에서 말했듯이, 하나의 큰 문제를 작은 문제들로 나누어 생각해보는 것이 목표입니다. 따라서, 한 번에 1개씩 추출을 해보겠습니다. 

 

즉, 5개중 하나만 우선 뽑아보겠습니다. 2가 나왔네요. 그렇다면 남은 동전에는 1, 3, 4, 5가 쓰여져 있겠군요.
즉 남은 4개의 동전들 중 나머지 2개를 뽑으면 되는 것입니다.

 

comb(list, num)을 list에서 num만큼 추출할 때 나오는 모든 결과를 반환하는 함수라고 할 때, 

comb([1,2,3,4,5], 3)를 구할 때에 있어서 [2] + comb([1,3,4,5],2)이 포함이 되겠습니다.

 

그렇다면 비슷한 논리로 comb([1,2,3,4,5], 3) 은 [i] + comb([1,2,3,4,5]-[i],2)를 i=0,1,2,3,4에 대해서 각각을 합집합한 것과 같을까요?

 

그렇지 않습니다. 이 이유는 간단합니다. 조합은 말 그대로 골랐을 때 추출된 item의 종류만이 중요합니다. 따라서 순서는 고려되지 않는다고 위에서도 언급했습니다. 그렇기에 단순히 위와같이 반복문을 통해 계산을 한다면 중복된 경우가 발생하게 됩니다. 예를 들자면 [1,2,3], [2,3,1]은 조합의 입장에서는 서로 같지만, 반복문을 통해서 나온 결과로는 두 개는 서로 다른 근원사건이 되는 것입니다. 따라서 우리는 중복을 피해야 되겠습니다.

 

중복을 피하기 - 기준 세우기

가장 간단하고 효과적인 방법은 기준을 세워 그 기준에 따라 분류하는 것입니다. 그렇게 나누면 명백히 중복은 없을테니까요. 그렇다면 무엇을 기준으로 세워볼까요? 동전에 적힌 숫자중 가장 작은 숫자를 기준으로 해보겠습니다. 명백히 서로 다른 숫자가 적혀있기 때문에, 이러한 기준 설정에는 문제가 없겠습니다.

 

(1) 1일 경우 : [2,3,4,5] 에서 나머지 2개 추출

(2) 2일 경우 : [3,4,5] 에서 나머지 2개 추출

(3) 3일 경우 : [4,5] 에서 나머지 2개 추출 

(4) 4일 경우 : [5] 에서 나머지 2개 추출 

 

(4)의 경우를 살펴보면 [5]에서 2개를 추출하는 것은 불가능하다는 것을 알 수 있습니다. 따라서 (3)의 상태까지만 수행을 하면 되겠습니다.

 

(1)에서 새롭게 정의한 subproblem, 즉 [2,3,4,5] 에서 나머지 2개 추출하는 문제도 똑같은 기준으로 해결해봅시다.

 

(1') 2일 경우 : [3,4,5]에서 나머지 1개 추출

(2') 3일 경우 : [4,5]에서 나머지 1개 추출

(3') 4일 경우 : [5]에서 나머지 1개 추출

 

정리해보자면 

"같은 방법으로 조금씩 작은 문제를 풀어가고 있습니다". 또한,

"어떠한 지점에 이르면, 우리는 그 작동을 멈춥니다."

 

이와 같이 문제를 해결하는 것을 Recursive하게 문제를 해결하는 것입니다. 또 위 두 문장중 위의 것이 general case, 아래의 문장을 base case라고 합니다.

 

구현하기 - base case 

위의 예시들을 살펴봤을 때, 언제 작동을 멈췄다고 할 수 있나요? 크게 두 가지 경우가 있겠습니다.
1. 추출할 item 수가 추출의 대상의 크기보다 클 경우

2. 추출할 item 수가 1일 경우

 

1. 추출할 item 수가 추출의 대상의 크기보다 클 경우

 

정의되어 있지 않은 값이기 때문에, 그냥 빈 list객체를 반환합니다.

 

2. 추출할 item 수가 1일 경우

 

기준과 관계없이 가능한 추출의 대상에서 하나씩 추출하면 되겠습니다.

 

 

구현하기 - general case 

추출할 item의 개수 num이 위의 base case 어디에도 걸리지 않을 경우, 우리는 general case에 해당하는 명령어들을 수행하면 되겠습니다. 이는 위에서 설명했듯이, 만약 comb(list, num)을 (num>1) 수행할 때,

(1) comb(list[1:], num-1)

(2) comb(list[2:], num-1)

...

(N)  comb(list[len(list)-num+1], num-1)

 

즉, N번의 반복문을 통해서 각 기준에 대해서 comb 연산을 수행해 num -1 개씩 추출합니다.
이 때 N = len(list)-num+1임을 알 수 있겠습니다.

 

마지막으로 반환하는 형식을 정해봅시다. 우리는 반환하는 값이 list of list로 두고자 합니다.
따라서 base case에서 각 item에 대해서 한개의 원소를 갖는 singleton을 원소로 둔 다음,
recursion의 순서에 맞게 ["기준이 된 가장 먼저 나타나는 원소"] + 얻어진 comb 반환값(리스트 형식)

 

구현하기 - 종합

base case, general case를 종합하면 아래와 같이 구현이 가능하겠습니다.

 

def comb(population,num):
	ans = []
    ## 정의된 값인지 확인한다.
	if num > len(population): return ans
	## Base Case
	if num == 1:
		for i in population:
			ans.append([i])
    ## General Case
	elif num>1:
		for i in range(len(population)-num+1): ## i가 시작하는 값 - len(population) - (n-1)이고 이 때 n은 lst로부터 추출할 개수와 같다.
			for temp in comb(population[i+1:],num-1):
				ans.append([population[i]]+temp)

	return ans

실행해볼 경우, 적절하게 정답이 나오는 것을 알 수 있습니다.

 

---

이번 포스팅에서는 recursion과 combination에 대해서 알아보았습니다.
combination의 문제를 해결할 때 자연스럽게 그 문제가 갖는 subproblem property를 관찰해
recursion을 이용해 문제를 해결하였고, 그를 위해 general case, base case를 정의하였습니다.

 

다음 포스팅에서는 recursion과 permutation, 그리고 그 구현에 대해서 알아보도록 하겠습니다. 감사합니다.

 

---

함께 보면 좋은 글들

[1] learnandearn.tistory.com/19

 

[2] learnandearn.tistory.com/14

 

[3] learnandearn.tistory.com/15