Skip to content

Instantly share code, notes, and snippets.

@blogle
Created April 24, 2014 20:51
Show Gist options
  • Save blogle/11269091 to your computer and use it in GitHub Desktop.
Save blogle/11269091 to your computer and use it in GitHub Desktop.
efficient calculation of nCr using sets
def choose(n,k):
"efficient calculation of nCr using sets"
if n < k:
raise ValueError('n < k')
n_set, k_set = set(range(1,n+1)), set(range(1,k+1))
n_min_k_set = set(range(1,(n-k)+1))
if len(n_min_k_set) < len(k_set):
return product(list(n_set - k_set)) / product(list(n_min_k_set))
else:
return product(list(n_set - n_min_k_set)) / product(list(k_set))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment