The Number of Ways to Evenly Divide n Different Items into k Groups

The study of mathematical combinatorics really fascinates me. Last week while working on some code I needed a function to calculate the number of ways to evenly divide n different items into k equally-sized groups. This turns out to be a surprisingly difficult problem. For example, if n = 4 (and the items are A, B, C, D) and k = 2, then there are Choose(4,2) / 2 = 3 ways to evenly divide the 6 items:

(A,B) and (C,D)
(A,C) and (B,D)
(A,D) and (B,C)

Notice we have to divide Choose(4,2) by 2 to eliminate some duplicates. Now suppose we have n = 12 items and k = 4 groups and so the size of each group is 12/4 = 3. We can compute the number of ways to evenly divide the 12 items like this:

= [Choose(12,3) * Choose(9,3) * Choose(6,3) * Choose(3,3)] / 4!
= [220 * 84 * 20 * 1] / 24
= 15,680

First we choose any 3 items for the first group. Next we choose any 3 items from the remaining 12-3 = 9 items for the second group. Then choose any 3 items from the remaining 9-3 = 6 items, and finally choose 3 items from the remaining 3 items. We divide by 4! to eliminate duplicates like {(A,B,C), (D,E,F), (G,H,I), (J,K,L)} and {( J,K,L), (D,E,F), (G,H,I), (A,B,C)}.

Because these numbers can get really huge I coded up the solution in C# using the System.Numerics BigInteger type. I needed helper functions Choose() and Factorial() which are interesting sub-problems by themselves. Here is the Choose() function:

public static BigInteger Choose(int n, int k)
{
  if (n < 0 || k < 0)
    throw new Exception(“Invalid negative parameter in Choose()”);
  if (n < k)
    return 0;  // special case
  if (n == k)
    return 1;

  BigInteger delta, iMax;

  if (k < n – k) // ex: Choose(100,3)
  {
    delta = n – k;
    iMax = k;
  }
  else         // ex: Choose(100,97)
  {
    delta = k;
    iMax = n – k;
  }

  BigInteger ans = delta + 1;

  for (BigInteger i = 2; i <= iMax; ++i)
  {
    checked { ans = (ans * (delta + i)) / i; }
  }

  return ans;
} // Choose()

An interesting problem.

About these ads
This entry was posted in Software Test Automation. Bookmark the permalink.