I am interested to find an absolute value (not an approximation) of "combination without repetition" for given \$n\$ and \$k\$, or \$\binom{n}{k}\$.
The brute force solution would look like this
private static ulong Factorial(int x)
{
ulong res = 1;
while (x > 1)
{
res *= (ulong)x--;
}
return res;
}
public static int Combination0(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
return (int)(Factorial(n) / (Factorial(k) * Factorial(n - k)));
}
We can slightly optimize this solution, by finding \$\prod_{n\geq i>k}{i}\$ instead of \$\frac{n!}{(n-k)!}\$.
private static ulong Factorial(int x, int until = 0)
{
ulong res = 1;
while (x > until)
{
res *= (ulong)x--;
}
return res;
}
public static int Combination1(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
return (int)(Factorial(n, n - k) / Factorial(k));
}
But these two solutions have one significant problem - we are limited by ulong.MaxValue
, which is more than \$20!\$, but less than \$21!\$.
Another way to find the number of combinations, which doesn't have the previously described problem, is the Pascal's triangle.
public static int Combination2(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
int[] triangle = new int[k + 1];
triangle[0] = 1;
// expanding
int i = 0;
for (; i < k; i++)
{
for (int j = i + 1; j > 0; j--)
{
triangle[j] += triangle[j - 1];
}
}
// progressing
for (; i < n - k; i++)
{
for (int j = k; j > 0; j--)
{
triangle[j] += triangle[j - 1];
}
}
// collapsing
for (; i < n; i++)
{
int until = k - (n - i);
for (int j = k; j > until; j--)
{
triangle[j] += triangle[j - 1];
}
}
return triangle[k];
}
But the problem is that Combination2
is significantly slow.
I would appreciate any comments and suggestions for an improvement.
Update
@quasar and @henrik-hansen suggested the way to prevent overflow by calculating \$\prod_{0 \leq i < k}{\frac{n-i}{i+1}}\$.