Best way of calculating n choose k?

by

Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k):

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

I wrote it recursively because it’s so simple and pretty, but you could transform it to an iterative solution if you like.

More Related Contents:

  1. Finding all possible combinations of numbers to reach a given sum
  2. How do I find a factorial? [closed]
  3. Compute rank of a combination?
  4. How can I pair socks from a pile efficiently?
  5. What is tail recursion?
  6. Unique (non-repeating) random numbers in O(1)?
  7. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  8. Getting the closest string match
  9. Converting a Uniform Distribution to a Normal Distribution
  10. What distribution do you get from this broken random shuffle?
  11. Is there an O(n) integer sorting algorithm?
  12. Generate all binary strings of length n with k bits set
  13. Determine font color based on background color
  14. Nearest neighbors in high-dimensional data?
  15. What algorithm gives suggestions in a spell checker?
  16. How can I measure the similarity between two images? [closed]
  17. Generate all unique substrings for given string
  18. How to efficiently build a tree from a flat structure?
  19. Sum-subset with a fixed subset size
  20. design a stack such that getMinimum( ) should be O(1)
  21. How to check if line segment intersects a rectangle?
  22. Calculate largest inscribed rectangle in a rotated rectangle
  23. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  24. Iterating over a Binary Tree with O(1) Auxiliary Space
  25. “Rounding” colour values to the nearest of a small set of colours
  26. Can an array be grouped more efficiently than sorted?
  27. Convert light frequency to RGB?
  28. Best way to find a point on a circle closest to a given point
  29. Algorithm to list all unique permutations of numbers contain duplicates
  30. Postfix notation to expression tree

Leave a Comment