Combination and factorial

Question

Combinations is how many ways to take k elements from n element. Combination is different from permutation in that order does not matter in combination. Combination is used a lot in poker calculations. Those are combinations used a lot in poker that I know are correct.

In Fast there are a number of terms that cancel out so I avoid them.

Please review for style and efficiency.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Numerics;
namespace CodeReview01
{
 class Program
 {
 static void Main(string[] args)
 {
 for (int i = 2; i <= 10; i++)
 {
 BigInteger factorial = Factorial(i);
 Debug.WriteLine($"factorial({i}) = {factorial}");
 }
 Debug.WriteLine("");
 int n = 3;
 int k = 2;
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}");
 n = 4;
 k = 2;
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}");
 n = 45;
 k = 2;
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}"); 
 n = 52;
 k = 2;
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}");
 n = 52;
 k = 5;
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}");
 n = 52;
 k = 7;
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Debug.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}");
 Debug.WriteLine("");
 }
 public static BigInteger Factorial (int n)
 {
 if(n < 1)
 {
 throw new IndexOutOfRangeException();
 }
 BigInteger factorial = 1;
 for(int i = 2; i <= n; i++)
 {
 factorial *= i;
 }
 return factorial;
 }
 public static int CombinationFact(int n, int k)
 {
 if(n < k)
 {
 throw new IndexOutOfRangeException();
 }
 if (n < 1 | k < 1)
 {
 throw new IndexOutOfRangeException();
 }
 if (n == k)
 {
 return 1;
 }
 int combination = (int)(Factorial(n) / Factorial(k) / Factorial(n - k)); 
 return combination;
 }
 public static int CombinationFast(int n, int k)
 {
 BigInteger combination = 1;
 // n * (n-1) * (n-2) * (n-3) * (n - 4) ... 2 * 1/ 
 // / k * (k-1) ... * 2 * 1 
 // / (n-k) * ... 2 * 1_
 for(int i = k+1; i <=n; i++)
 {
 combination *= i;
 }
 BigInteger denominator = 1;
 for (int i = 2; i <= (n - k); i++)
 {
 denominator *= i;
 }
 combination /= denominator;
 return (int)combination;
 }
 }
}

• Peter Taylor: Efficiency depends on use cases. Should we understand from the references to poker that you will be calling the methods frequently but with n on the order of 52? Or are you interested in efficiency when n is on the order of 1000000? If the latter (large n) case, are you only interested in k very close to 0 or n, or in intermediate values of k too?
• paparazzo: @PeterTaylor In poker I am not making the call in a simulation so speed is not that critical.

Answer 1

int is IMO not an appropriate type in this domain. I would use ulong or maybe BigInteger

If you for instance run the following test, both CombinationFact() and CombinationFast() runs out of range:

 n = 52;
 k = 9;
 Console.WriteLine($"Combin({n}, {k}) = {CombinationFact(n, k)}");
 Console.WriteLine($"Combin({n}, {k}) = {CombinationFast(n, k)}");

---

I would use throw new ArgumentOutOfRangeException(nameof(n)); instead of throw new IndexOutOfRangeException();

---

You don't need the extra variable combinations:

int combination = (int)(Factorial(n) / Factorial(k) / Factorial(n - k)); return combination;

Just return the result of the calculation:

 return (int)(Factorial(n) / Factorial(k) / Factorial(n - k)); 

---

Both of your algorithms is rather limited in use due to the int-conversion, but you could change the fast version to something like:

public ulong CombinationFast(ulong n, ulong k)
{
 ulong count = n;
 for (ulong x = 1; x <= k - 1; x++)
 {
 count *= (n - x);
 count /= x;
 }
 return count / k;
}

Update

Because 10!/(4!(10-4)!) == (10!/6!(10-6)!) it is possible to optimize the calculation for k > n/2:

public ulong CombinationFast(ulong n, ulong k)
{
 if (k > n / 2)
 k = n - k;
 ulong count = n;
 for (ulong x = 1; x <= k - 1; x++)
 {
 count *= (n - x);
 count /= x;
 }
 return count / k;
}

The above algorithms is an implementation of this expression.

A more literal version should maybe be:

public ulong CombinationFast(ulong n, ulong k)
{
 if (k > n / 2)
 k = n - k;
 ulong count = 1;
 for (ulong x = 0; x < k; x++)
 {
 count *= (n - x);
 count /= (x + 1);
 }
 return count;
}

• Nikita B: I would also add meaningful messages to exceptions. OutOfRange exception should clearly state what range is considered valid.
• paparazzo: The last seems to work but I cannot figure out why.
• user73941: @paparazzo: Yes, it works due to the relation between the sequences of (n-x) and x
• paparazzo: If you have some time I wish you would explain it.
• Peter Taylor: @paparazzo, re "The last seems to work but I cannot figure out why": have you noticed that this is essentially identical to this question from yesterday?

Answer 2

 public static BigInteger Factorial (int n)
 {
 if(n < 1)
 {
 throw new IndexOutOfRangeException();
 }

Two things:

1. \0ドル! = 1\$ is an important case which should be handled.
2. The appropriate exception would be ArgumentOutOfRangeException(nameof(n)).

---

 public static int CombinationFact(int n, int k)
 {
 if(n < k)
 {
 throw new IndexOutOfRangeException();
 }
 if (n < 1 | k < 1)
 {
 throw new IndexOutOfRangeException();
 }

For many applications of binomial coefficients it's preferable to have

 if (k < 0 || k > n)
 {
 return 0;
 }

rather than to throw an exception.

---

 // n * (n-1) * (n-2) * (n-3) * (n - 4) ... 2 * 1/ 
 // / k * (k-1) ... * 2 * 1 
 // / (n-k) * ... 2 * 1_

This comment is rather hard to read. What's wrong with n! / k! / (n-k)!?

 BigInteger denominator = 1;
 for (int i = 2; i <= (n - k); i++)
 {
 denominator *= i;
 }
 combination /= denominator;

Why not just this?

 for (int i = 2; i <= (n - k); i++)
 {
 combination /= i;
 }

Also, if you're going with either one or two loops of length k it's worth using the symmetry that \$\binom{n}{k} = \binom{n}{n-k}\$. This can be as simple as k = Math.Min(k, n - k);.

---

You asked about efficiency. Both approaches do multiplications of rather large BigIntegers. There's also no caching. If you know that n will always be small then there's a lot to be said for caching the first n+1 rows of Pascal's triangle, calculated by adding the previous row to itself offset by one.

On the other hand, if n can be large then multiplication is faster than building the triangle, but you can improve the simple multiplication approach by clustering numbers so that you do lots of multiplications with small numbers and few with large numbers. This makes the code more complicated but gives a notable performance improvement.

If performance is really an issue for large n, the best approach seems to be to factor numbers up to n into primes, use addition and subtraction to work out the power to which each prime should be raised, and then multiply the primes together in the way suggested in the previous paragraph.

• paparazzo: The comment is like that to show terms cancel to come to the fast (er) algorithm. I want to see the denominator for validation.