조합(Combination)의 코드화

 

조합(Combination)의 코드화에 대해 글을 작성해보려한다.

 

조합을 코드화하기 위한 아이디어를 생각해보자.

 

 

[4, 3, 2, 1]에서 성분이 2개인 조합을 구하는 방식은 다음과 같다.

먼저 4를 고정해놓고 뒤의 숫자를 1개 고른다.

그 후 4를 제외하고 3을 고정, 뒤의 숫자를 1개 고른다.

 

그런데 여기서 고정된 성분을 따로 떼어놓고 생각해보자.

 

 

고정된 성분 4를 제외하고 생각해보면, 이는 [3, 2, 1]이라는 배열에서 성분이 1개인 조합을 구한 것에 성분 4를 추가한 것과 같다.

이를 통해 list에서 n개의 조합을 구하는 알고리즘을 짜보자.

 

1. 고정할 성분을 선택

2. 이를 제외한 뒤의 배열에서 n-1개의 조합을 구함

3. 이 조합에 고정한 성분을 추가 

4. 다음 고정 성분을 선택한 후 반복

 

이를 알고리즘으로 표현하면 다음과 같다.

 

def combination(list, count):
  if count == 1:
    return [[i] for i in list]
        
  combi_list = []
        
  for i in range(len(list)): #다음 고정 성분을 선택한 후 반복
    fix_element = list[i] #고정할 성분을 선택
        
    #이를 제외한 뒤의 배열에서 n-1개의 조합을 구함
    for combi in combination(list[i+1:], count - 1):
      combi_list.append([fix_element] + combi) # 이 조합에 고정한 성분을 추가
            
  return combi_list

 

Reference

Python 순열, 조합 구현하기