중복 조합

SQL SELECT에서 JOIN으로 만들어질 수 있는 SELECT 구문의 개수를 세려고 했다. (SQL을 모르면 다음 문단으로 가도 상관이 없다) 내 문제는, Join 할 테이블이 4개가 있는데 여기서 같은 Table을 JOIN해도 된다는 조건이 있는 상황이다.

중복 조합

위 문제는 결국 ‘중복 선택이 가능하고, 순서는 상관없는’ 조합을 구하는 문제와 같다. 일반 조합을 구하는 공식은 알고 있었지만 그 때는 중복 선택이 불가능하다. 중복 조합을 구하는 공식이 있을까?

당연히 있다. 위키피디아 페이지에서 찾았는데, 아래와 같은 ‘일반 조합 계산 식’으로 바꿀 수 있다.

$$_nH_k = _{n+k-1}C_k$$

앞서 소개한 문제에서는, 테이블 4개 중 ‘2개, 3개, 4개’ 로 중복 조합한 경우의 수를 합하면 되겠다.

$$_{4+2-1}C_2  +\ _{4+3-1}C_3\!  +\ _{4+4-1}C_4\\ = _5C_2 +\ _6C_3 +\ _7C_4\\= 10 + 20 + 35$$

참고로 이 공식은 아래 Python 코드를 통해 검증이 가능하다. 윗 부분이 중복 조합, 아래 부분이 변환된 일반 조합식이다.

import itertools

# Combination with replacement/repetition
print len(list(itertools.combinations_with_replacement(range(4), 2)))
print len(list(itertools.combinations_with_replacement(range(4), 3)))
print len(list(itertools.combinations_with_replacement(range(4), 4)))

# Combination
print len(list(itertools.combinations(range(5), 2)))
print len(list(itertools.combinations(range(6), 3)))
print len(list(itertools.combinations(range(7), 4)))