[Python][Algorithm] 조합 Combination

조합은 기본적으로 중복되지 않도록 원하는 만큼을 뽑는 경우입니다. 

이 이상으로 조합이 가지는 의미를 파악한다면 이를 코드로 작성하는 것은 쉬운 일입니다. 

 

예제를 통해서 시야를 넓혀봅시다. 

 

Sequence = [1,2,3,4] 에서 2개를 뽑는데 1을 뽑고난 뒤에는 2,3,4 세 가지 중에서 하나를 뽑을 수 있습니다. 

그림으로 나타내면 아래와 같습니다.

 

뽑기

 리스트 [1, ?] 를 현재 리스트라고 하면 전체 수열에서 현재 리스트에 1을 담은 상태에서 2,3,4 만 바뀌고 있습니다.

이를 코드로 나타낸다면 2가지 방법이 있는데 

1. 인덱스를 이용해서 값을 바꿉니다. 

2. 기존 값을 빼고 새로운 값을 넣습니다. 

 

이 중에서 조합을 구하는 데 사용되는 방법은 두 번째 입니다. 

 

이 방법을 일반적으로 적용하면 조합을 구현할 수 있습니다. 핵심이 되는 부분만 살펴보고

나머지는 아래 깃허브 코드를 보고 확인하시면 됩니다.

 

주요 부분은 append 와 recursive, pop을 이용하는데, 

2,3,4 를 순서대로 넣어준 것처럼 for 문을 사용한다는 점 입니다.

def comb(sequence, start, total, index, curr, result):
    if index == 0:
       result.append(curr[:]
        return
 
    for i in range(start, total):
     curr.append(sequence[i]
        comb(sequence, i+1, total, index-1, curr, result)
      curr.pop()