Calculating the Amount of Combinations

by

Here’s an ancient algorithm which is exact and doesn’t overflow unless the result is to big for a long long

unsigned long long
choose(unsigned long long n, unsigned long long k) {
    if (k > n) {
        return 0;
    }
    unsigned long long r = 1;
    for (unsigned long long d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

This algorithm is also in Knuth’s “The Art of Computer Programming, 3rd Edition, Volume 2: Seminumerical Algorithms” I think.

UPDATE: There’s a small possibility that the algorithm will overflow on the line:

r *= n--;

for very large n. A naive upper bound is sqrt(std::numeric_limits<long long>::max()) which means an n less than rougly 4,000,000,000.

More Related Contents:

  1. Creating all possible k combinations of n items in C++
  2. Create an algorithm that asks the user for two positive numbers, call them “first” and “last”, and prints the sum of all the numbers between first [closed]
  3. What is the most effective way for float and double comparison?
  4. How to implement classic sorting algorithms in modern C++?
  5. Fast bignum square computation
  6. Detecting endianness programmatically in a C++ program
  7. Determine if two rectangles overlap each other?
  8. Which is the fastest algorithm to find prime numbers?
  9. Algorithm to convert RGB to HSV and HSV to RGB in range 0-255 for both
  10. Rounding up to the nearest multiple of a number
  11. Magic number in boost::hash_combine
  12. How do I calculate the week number given a date?
  13. Where can I get a “useful” C++ binary search algorithm?
  14. How to get a random element from a C++ container?
  15. LRU cache design
  16. c++ sort keeping track of indices [duplicate]
  17. Determining if a number is prime
  18. How to add two numbers without using ++ or + or another arithmetic operator
  19. Are there any better methods to do permutation of string?
  20. Reorder vector using a vector of indices [duplicate]
  21. Finding all the unique permutations of a string without generating duplicates
  22. Fastest algorithm for primality test [closed]
  23. Efficiently getting all divisors of a given number
  24. Cut set of a graph, Boost Graph Library
  25. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  26. What’s time complexity of this algorithm for finding all combinations?
  27. How to find and replace all occurrences of a substring in a string?
  28. Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]
  29. Good C++ solutions to the “Bring all the zeros to the back of the array” interview challenge
  30. Order Statistic Tree in C++

Leave a Comment