counting combinations and permutations efficiently

by

if n is not far from r then using the recursive definition of combination is probably better, since xC0 == 1 you will only have a few iterations:

The relevant recursive definition here is:

nCr = (n-1)C(r-1) * n/r

This can be nicely computed using tail recursion with the following list:

[(n – r, 0), (n – r + 1, 1), (n – r + 2, 2), …, (n – 1, r – 1), (n, r)]

which is of course easily generated in Python (we omit the first entry since nC0 = 1) by izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Note that this assumes r <= n you need to check for that and swap them if they are not. Also to optimize use if r < n/2 then r = n – r.

Now we simply need to apply the recursion step using tail recursion with reduce. We start with 1 since nC0 is 1 and then multiply the current value with the next entry from the list as below.

from itertools import izip

reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1)

More Related Contents:

  1. How to generate all permutations of a list?
  2. Evenly distributing n points on a sphere
  3. What is the best way to get all the divisors of a number?
  4. Find all combinations of a list of numbers with a given sum
  5. How did Python implement the built-in function pow()?
  6. Algorithm to find which number in a list sum up to a certain number
  7. How do I generate all permutations of a list?
  8. Why does Python’s itertools.permutations contain duplicates? (When the original list has duplicates)
  9. How to find integer nth roots?
  10. Heap’s algorithm permutation generator
  11. Getting the subsets of a set in Python
  12. Fastest way to list all primes below N
  13. Quicksort with Python
  14. Python and Powers Math
  15. Math operations from string [duplicate]
  16. Difference between the built-in pow() and math.pow() for floats, in Python?
  17. Python: sort function breaks in the presence of nan
  18. How to trace the path in a Breadth-First Search?
  19. How to get all combinations of length n in python
  20. Statistics: combinations in Python
  21. Rotate image and crop out black borders
  22. How to invert a permutation array in numpy
  23. Adjacency List and Adjacency Matrix in Python
  24. Linear regression of arrays containing NANs in Python/Numpy
  25. Multiple variables in SciPy’s optimize.minimize
  26. How to hash a string into 8 digits?
  27. Python floating-point math is wrong [duplicate]
  28. How to pad a string with leading zeros in Python 3 [duplicate]
  29. How do I generate permutations of length LEN given a list of N Items?
  30. Python – Removing overlapping lists

Leave a Comment