[Algorithm] 조합을 구현해보자

이번 포스트는 파이썬에서 조합을 구현하는 방식에 대해 이야기해보려 합니다.
 
크게 두 가지 방식으로 구현해보겠습니다.
1. 중첩 반복문
2. 재귀

---

중첩 반복문으로 5C3 구현하기

'ABCDE' 문자열 요소들에 대해 for를 활용하여 5C3을 구현해보겠습니다.

arr = 'ABCDE'
N, R = len(arr), 3          # 5C3 = 10

for i in range(N - 2):              # 첫 번째 요소 선택
    for j in range(i + 1, N - 1):   # 두 번째 요소 선택
        for k in range(j + 1, N):   # 세 번째 요소 선택
            print(arr[i], arr[j], arr[k])

 

처음 보면 코드가 좀 난해할 수 있습니다.

그렇다면 그림으로 이해해봅시다.

 

이제 패턴이 좀 보이지 않나요~?

---

재귀로 5C3 구현하기

arr = 'ABCDE'
N, R = len(arr), 3
pick = [0] * R    # 선택한 R개 저장

def comb(k, s):   # s: 반복의 시작
    if k == R:
        print(pick)
    else:
        remain = R - (k + 1)
        for i in range(s, N - remain):
            pick[k] = arr[i]
            comb(k + 1, i + 1)

comb(0, 0)

 

여기서 핵심은 remain 변수를 통해 반복의 구간을 잘 설정해주는 것입니다.