Combination

From Algorithmist
Jump to navigation Jump to search

The Combination function is used in matematics to determine the possible number of available choices from a given group. It has two varibles: n, the number of items available to pick, and k, the number of items to pick.

This function appears in Pascal's Triangle.

Calculation[edit]

Combination is normally calculated by factorials, but the straight forward calculation may cause overflow on some systems:

combination (n, k) = factorial (n) / (factorial(k) * factorial(n-k))

The brute force method, while simple, is highly inefficient, even with dynamic programming:

combination (n, k) = combination (n-1, k) + combination (n-1, k-1)

In most problems, a more efficient method is as follows:

combination (n,k) =
{
  c=1
  for (i = 0; i < k; ++i)
  {
    c = c * (n - i)
    c = c / (i + 1)
  } 
}