파이썬 itertools의 조합 Combinations 구현

개요

파이썬의 itertools 라이브러리에는 데이터를 셀 수 있도록 도와주는 유용한 기능들이 있다.

순열을 만들어주는 permutations도 있고 가장 긴 길이를 가진 객체를 기준으로 객체들을 인덱스 단위로 묶어주는 zip_longest도 있다.

itertools에는 조합을 만들어주는 Combinations도 있는데, 이는 어떻게 작동되고 구현되는 것일까?

 

조합이란?

말 그대로 수학식 nCr이다.

서로 다른 n개의 원소를 가지는 어떤 집합을 조합이라고 한다.

 

수학식으로 보자면 아래와 같다.

그럼 이 조합이 파이썬에서는 어떻게 나타날까?

 

파이썬에서 조합이 기능하는 방법

from itertools import combinations

arr = [1,2,3,4,5]
com_arr = list(combinations(arr, 3))

print(com_arr)

#
[(1, 2, 3), (1, 2, 4), (1, 2, 5),
(1, 3, 4), (1, 3, 5), (1, 4, 5),
(2, 3, 4), (2, 3, 5), (2, 4, 5),
(3, 4, 5)]
#

위처럼 조합의 묶음은 튜플로 감싸져 있고 전체적으로는 리스트로 감싸져 있는 형태로 조합을 만들어준다.

중복조합이 아니므로 같은 조합은 존재하지 않는다.

중복조합을 만들고 싶다면, from itertools import combinationswith_replacement을 활용하면 된다.

 

그럼 저렇게 조합을 만들어주는 combination은 어떻게 구현된 걸까?

 

조합을 구현하는 방법

def my_combinations(iterable, number):
    arr = [None for _ in range(number)]
    result = []
    
    def combination(depth, start):
        if depth == number:
            result.append(tuple(arr))
        else:
            for i in range(start, len(iterable)):
                arr[depth] = iterable[i]
                combination(depth + 1, i + 1)
    combination(0, 0)
    
    return result

중요한 점은 시작 지점을 함수에 넣어주고 for문이 돌 때 시작지점이 start가 되도록 해야 한다.

조합은 한번 나온 숫자의 조합이 포함되지 않기 때문에, 숫자의 재사용을 막기 위해서 시작 지점을 저렇게 명시해주어야 한다.

이론은 어렵다. 그냥 코드 외우는 게 편한 것 같다.