조합을 구하는 파이썬 내장함수가 있지만 (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 에 작성했습니다.

+ Random Posts