[Python] 조합(combination) 개수 계산하기

조합을 구하는 파이썬 내장함수가 있지만 (from itertools import combination) 이 함수는 리스트 조합의 결과를 반환합니다.

from itertools import combinations lists = [1,2,3] a = list(combinations(lists, 2)) print(list(a)) # [(1, 2), (1, 3), (2, 3)]

따라서 단순히 개수를 확인할 때 사용하기에는 적합하지 않습니다. 

이러한 이유로 아래와 같이 단순 개수만 반환하는 로직을 구현했습니다.

import operator as op from functools import reduce def nCr(n, r): if n < 1 or r < 0 or n < r: raise ValueError r = min(r, n-r) numerator = reduce(op.mul, range(n, n-r, -1), 1) denominator = reduce(op.mul, range(1, r+1), 1) return numerator // denominator print(nCr(3, 2)) # 3

해당 로직에서 min(r, n-r)을 사용한 이유는  nCr(n,r)과 nCr(n, n-r)은 동일하기 때문에 좀 더 속도를 빨리 하고자 들어간 로직입니다. 

reduce()에서 op.mul을 사용한 이유는 https://brownbears.tistory.com/458 에 작성했습니다.