Investigating Basic Combinatorics

In programming and in math we are often interested in how many possible combinations of objects exist. For example: how many 5-hand cards can be made from a 52-card deck? In mathematics these are referred to as combinatorics problems. Many basic combination problems can be evaluated with the formula:

The formula is verbally stated as “N choose R”. An C# algorithm we might use to evaluate ⁿC_r could look like this:

static long CombinationsOf(long n, long r)
{
	long combinations = 1;
	if ( r < n)
	{

		for (long i = 1; i <= n; i++)
		{
			combinations *= i;
		}
		for (long i = 1; i <= r; ++i)
		{
			combinations /= i;
		}
		for (long i = 1; i <= (n - r); ++i)
		{
			combinations /= i;
		}

	}
	else
	{
		throw new NotImplementedException();
	}
	return combinations;

}

In the first for loop we will find the value of n!, the second for loop will divide by r!, and finally the third will divide by (n-r!). Let's use the function in a console application to test the example problem: "Ignoring order, how many 5-hand cards can be made from a 52-card deck?" In this case, we have 52 unique cards (n=52) and we want to see how many 5 card combinations are possible (r=5).

static void Main(string[] args)
{
	var stopwatch = new Stopwatch();
	stopwatch.Start();

	int n= 52;
	int r = 5;

	var nCr = CombinationsOf(n, r);
	stopwatch.Stop();

	Console.WriteLine("Time Elapsed: " + stopwatch.Elapsed);
	Console.Write(n.ToString() + " choose " + r.ToString() + " = " +nCr.ToString() );

	Console.ReadLine();
}

Time Elapsed: 00:00:00.0004409
52 choose 5 = 0

Yikes. Something's not right. So where did we go wrong? As it turns out our function is correct but it can only evaluate up to n = 20. If n≥21 then the product resulting from the first for-loop will exceed long.MaxValue, but the bit wise operations will continue without consideration for this scenario. (Note that it is possible to get a positive, negative, or zero result that is incorrect using this choice of algorithm.)

Let's plug in n = 10 and r = 3 into the formula and solve by hand.

n! = 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2

(n-r)! = 7! = 7 * 6 * 5 * 4 * 3 * 2
r! = 3! = 3 * 2

7!3! = (7 * 6 * 5 * 4 * 3 * 2)(3 * 2)

10! / (7!3!) = (10 * 9 * 8) / (3 * 2) = 10 * 3 * 4 = 120

Now, let's plug in n = 52 and r = 5 into the formula and solve by hand.

n! = 52! = 52 * 51 * .... 3 * 2
(n - r)!r! = 47! = (47 * 46 * ... 3 * 2)(5 * 4 * 3 * 2)

52! / (47!5!) = 52 * 51 * 50 * 49 * 48 / (5 * 4 * 3 * 2) = 52 * 51 * 10 * 49 * 2

The final calculation is fed into a calculator and the result is 2,598,960, which is well within the long data type limits. In both cases we can see that n! is significantly reduced when divided by the terms of the denominator. (In fact the closer as r->n or r -> 1, the smaller ⁿC_r will be. The converse of this is that ⁿC_r is increases as r->n/2 and is maximized when r = n/2 for even n and when r = n/2 ±.5 for odd n. This also implies ⁿC_r = ⁿC_{n - r}).

In order to maximize the number of possible permutations returned from standard .NET data types (not including System.Numerics.BigInteger) we will want to iterate through division by the denominator in real-time as we multiple through the terms in the numerator. A strategy for this approach might look like this:

static ulong CombinationsOf(ulong n, ulong r)
{
	double combinations = 1;
	ulong bigDenominator = n - r >= r ? n - r : r;
	ulong smallDenominator = n - r < r ? n - r : r;
	ulong j = 1;
	for (ulong i = n; i > 0; --i)
	{
		if(i > bigDenominator)
		{
			combinations *= i;
		}

		if(j <= smallDenominator)
		{
			combinations /= j;
		}
		j++;
	}
	return (ulong)combinations;
}

Some things to note about this approach: Since we know a valid value will be positive we've chosen ulong as the return type. This gives us a max_value twice that of long. The double data type is used to account for fractional values of combinations that will result prior to the completion of the algorithm. It is possible to change the algorithm to hold values until they can be evenly divided, but this approach suits this demonstration.

When we iterate through ⁿC_n/2, we don't run into any issues until n = 68. A future post will address calculating permutations beyond the limits of standard .NET data types.