조합/중복조합 [파이썬]

역시 파이썬이 더 재미있다.

def factorial(n):
  if n <= 1:
    return 1
  else:
    result = 1
    for i in range(2, n+1):
      result *= i
    return result

# nCk = n! / (n-k)! * k!
def comb_slow(n, k):
  return factorial(n) / (factorial(k)*factorial(n-k))
  
print(comb_slow(6,3))

def comb_fast(n, k):
  numerator = 1
  denominator = 1
  k = min(n-k, k)  # nCk에서 더 적은 수로 계산하기 위해서.
  den_list = []
  num_list = []
  for i in range(k):  # 기존 소스에서 이곳을 변경함.
    denominator *= i + 1
    numerator *= n-i
    den_list.append(i+1)
    num_list.append(n-i)
  print('den_list={}'.format('*'.join(str(x) for x in den_list)))
  print('num_list={}'.format('*'.join(str(x) for x in num_list)))
  
  return numerator/denominator
  
print(comb_fast(6,3))

# 번외 중복조합
# nHr = n+r-1Cr
def ham(n, k):
  return comb_fast(n+k-1, k)
  
print(ham(6, 3))

# 참고문헌 : https://smlee729.github.io/python/algorithm/2015/03/08/1-nchoosek.html