Combination "Ordination"

I recently needed a way to convert lots of combinations to ordinal numbers quickly.  Google wasn't being helpful.  So I made one up.

To Do What Now?

Let's say I have a program that's dealing 7-card hands from a deck of 52 cards.  There are $\binom{52}{7}\text{=}$133,784,560 different possible hands that can be dealt.  I want a quick way to convert any given combination of seven cards to its corresponding ordinal number from 0 to 133,784,559.  And by "quick" I mean taking minimal time to "ordinate" millions of combinations.

Counting Combinations

If we happen to be dealt card “0”, then with 51 cards left in the deck and 6 more cards to choose, there are $\binom{51}{6}$ ways to choose the rest of the hand.  In other words, there are $\binom{51}{6}$ possible hands containing card "0".

If however, the lowest card in our hand is “3”, then there are only 48 higher cards from which the other 6 were chosen.  So there are only $\binom{48}{6}$ combinations having "3" as the lowest card.  With "5" as the lowest card, there are only $\binom{46}{6}$ combinations, etc.

Given some lowest card (say, "0", "1", or "2"), the subset of combinations containing it, which have “3” as their second lowest card, is $\binom{48}{\bf{5}}$, because there are five more cards in the hand, selected from the 48 cards higher than "3".  So given some $\text{N-1}$ lowest cards, the subset of the combinations containing them, which have $\text{X}$ as their $\text{N}$th lowest card, is $\binom{51-X}{7-N}$.

So I built a table representing these combination counts like this:

	0	1	2	3	4	5	6	…	45	46	47	48	49	50	51
Card 0	$\binom{51}{6}$	$\binom{50}{6}$	$\binom{49}{6}$	$\binom{48}{6}$	$\binom{47}{6}$	$\binom{46}{6}$	$\binom{45}{6}$	…	$\binom{6}{6}$	0	0	0	0	0	0
Card 1	0	$\binom{50}{5}$	$\binom{49}{5}$	$\binom{48}{5}$	$\binom{47}{5}$	$\binom{46}{5}$	$\binom{45}{5}$	…	$\binom{6}{5}$	$\binom{5}{5}$	0	0	0	0	0
Card 2	0	0	$\binom{49}{4}$	$\binom{48}{4}$	$\binom{47}{4}$	$\binom{46}{4}$	$\binom{45}{4}$	…	$\binom{6}{4}$	$\binom{5}{4}$	$\binom{4}{4}$	0	0	0	0
Card 3	0	0	0	$\binom{48}{3}$	$\binom{47}{3}$	$\binom{46}{3}$	$\binom{45}{3}$	…	$\binom{6}{3}$	$\binom{5}{3}$	$\binom{4}{3}$	$\binom{3}{3}$	0	0	0
Card 4	0	0	0	0	$\binom{47}{2}$	$\binom{46}{2}$	$\binom{45}{2}$	…	$\binom{6}{2}$	$\binom{5}{2}$	$\binom{4}{2}$	$\binom{3}{2}$	$\binom{2}{2}$	0	0
Card 5	0	0	0	0	0	$\binom{46}{1}$	$\binom{45}{1}$	…	$\binom{6}{1}$	$\binom{5}{1}$	$\binom{4}{1}$	$\binom{3}{1}$	$\binom{2}{1}$	$\binom{1}{1}$	0
Card 6	0	0	0	0	0	0	1	…	1	1	1	1	1	1	1

Table A

The “0”s in the table represent impossibilities because, for instance, the second lowest card can’t be lower than “1”, and the second highest card can’t be higher than “50”.

Row 6 is essentially saying that any given seven cards make up exactly one combination.

Calculating An Ordinal

We can define a given combination's (zero based) ordinal number as the count of all combinations which "come before" it.

So if our lowest card is “2”, we can say that there are TableA[0][0]$\text{+}$TableA[0][1] $\text{=}\binom{51}{6}\text{+}\binom{50}{6}$ combinations which come before those starting with “2”.

And if our second lowest card is “5”, we can say there are TableA[1][3]$\text{+}$TableA[1][4] $\text{=}\binom{48}{5}\text{+}\binom{47}{5}$ combinations of those starting with “2”, which come before those having “5” as the second card.  In other words, for each card, we count the combinations after the previous card value and before the given card value.  So before all {2,5,X,X,X,X,X} combinations, there are $\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{48}{5}\text{+}\binom{47}{5}$ combinations.

This is essentially my solution.  A combination’s ordinal is the count of all combinations which come before it, which we can calculate quickly by summing table entries.

Folding It Up

But we can do it more quickly if we fold the table up a bit.

So I replaced each entry with the sum of the entries that came before it in the row, creating this table:

	0	1	2	3	4	5	…
Card 0	0	$\binom{51}{6}$	$\binom{51}{6}\text{+}\binom{50}{6}$	$\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{49}{6}$	$\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{49}{6}\text{+}\binom{48}{6}$	$\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{49}{6}\text{+}\binom{48}{6}\text{+}\binom{47}{6}$	…
Card 1	0	0	$\binom{50}{5}$	$\binom{50}{5}\text{+}\binom{49}{5}$	$\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}$	$\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}\text{+}\binom{47}{5}$	…
Card 2	0	0	0	$\binom{49}{4}$	$\binom{49}{4}\text{+}\binom{48}{4}$	$\binom{49}{4}\text{+}\binom{48}{4}\text{+}\binom{47}{4}$	…
Card 3	0	0	0	0	$\binom{48}{3}$	$\binom{48}{3}\text{+}\binom{47}{3}$	…
Card 4	0	0	0	0	0	$\binom{47}{2}$	…
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

Table B

Now we can see, at TableB[0][0], that 0 combinations come before those with “0” as the lowest card, and at TableB[0][1] that $\binom{51}{6}$ combinations come before those with “1” as the lowest card.  And so before all {2,5,X,X,X,X,X} combinations there are TableB[0][2]$\text{+}$(TableB[1][5]-TableB[1][3]) combinations, which again is $\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{48}{5}\text{+}\binom{47}{5}$ combinations.  In other words we get the sum for each card with at most two table reads and a subtraction regardless of the size of the gaps between values.

But we can still do better.  Since the subtraction for one card is always from the column following the addition for the previous card, we can fold that subtraction in as well, creating this table:

	0	1	2	3	4	5	…
Card 0	0	$\binom{51}{6}$ $-$ $\binom{50}{5}$	$\left(\binom{51}{\bbox[2px]{6}}\text{+}\binom{50}{6}\right)$ $-$ $\left(\binom{50}{5}\text{+}\binom{49}{5}\right)$	$\left(\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{49}{6}\right)$ $-$ $\left(\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}\right)$	$\left(\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{49}{6}\text{+}\binom{48}{6}\right)$ $-$ $\left(\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}\text{+}\binom{47}{5}\right)$	$\left(\binom{51}{6}\text{+}\binom{50}{6}\text{+}\binom{49}{6}\text{+}\binom{48}{6}\text{+}\binom{47}{6}\right)$ $-$ $\left(\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}\text{+}\binom{47}{5}\text{+}\binom{46}{5}\right)$	…
Card 1	0	0	$\binom{50}{5}$ $-$ $\binom{49}{4}$	$\left(\binom{50}{5}\text{+}\binom{49}{5}\right)$ $-$ $\left(\binom{49}{4}\text{+}\binom{48}{4}\right)$	$\left(\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}\right)$ $-$ $\left(\binom{49}{4}\text{+}\binom{48}{4}\text{+}\binom{47}{4}\right)$	$\left(\binom{50}{5}\text{+}\binom{49}{5}\text{+}\binom{48}{5}\text{+}\binom{47}{5}\right)$ $-$ $\left(\binom{49}{4}\text{+}\binom{48}{4}\text{+}\binom{47}{4}\text{+}\binom{46}{4}\right)$	…
Card 2	0	0	0	$\binom{49}{4}$ $-$ $\binom{48}{3}$	$\left(\binom{49}{4}\text{+}\binom{48}{4}\right)$ $-$ $\left(\binom{48}{3}\text{+}\binom{47}{3}\right)$	$\left(\binom{49}{4}\text{+}\binom{48}{4}\text{+}\binom{47}{4}\right)$ $-$ $\left(\binom{48}{3}\text{+}\binom{47}{3}\text{+}\binom{46}{3}\right)$	…
Card 3	0	0	0	0	$\binom{48}{3}$ $-$ $\binom{47}{2}$	$\left(\binom{48}{3}\text{+}\binom{47}{3}\right)$ $-$ $\left(\binom{47}{2}\text{+}\binom{46}{2}\right)$	…
Card 4	0	0	0	0	0	$\binom{47}{2}$ $-$ $\binom{46}{1}$	…
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

Table C

Wrapping It Up

As it turns out, row 6 remains trivial through all transformations (TableC[6][X]$\text{=X-6}$), so we can do without it.  And since only card 6 (the highest card in the combination) can be "51", we don’t need column 51 either.  So the final table is 6x51 entries.

So now the ordinal of combination {A,B,C,D,E,F,G} $=$ ​TableC[0][A] $+​$ TableC[1][B] $+$ ​TableC[2][C] $+$ ​TableC[3][D] $+$ ​TableC[4][E] $+$ ​TableC[5][F] $+$ ​(G $-$ 6).

And that’s my full solution.

As you may have noted, there’s some air that can be squeezed out of that table, but only at the cost of extra operations in calculating the ordinal.

The biggest weakness of this approach is that it requires the combination to be sorted.

The Code

Here's the code:

// Calculate the number of unique combinations of K items which can be selected from N unique items.
template<typename T> T NChooseK(T n, T k)
{
   if(k > n)     return 0;
   if(k * 2 > n) k = n - k;
   if(k == 0)    return 1;

   T combos = n;
   for(T i = 2; i <= k; ++i)
   {
      combos *= (n - i + 1);
      combos /= i;
   }
   return combos;
}

// Generate a table for converting all (N-choose-K) combinations to unique, consecutive ordinals.
template<uint32_t N, uint32_t K> uint32_t const(& GetOrdinationTable())[K - 1][N - 1]
{
   static uint32_t ComboCount[K - 1][N - 1] = {0};

   static struct initializer
   {
      initializer()
      {
         for(uint32_t iK = 0; iK < K - 1; ++iK)
         {
            uint32_t Accumulated = 0;
            for(uint32_t iN = iK; iN < N - K + iK + 1; ++iN)
            {
               ComboCount[iK][iN] = Accumulated;
               Accumulated += NChooseK(N - iN - 1, K - iK - 1);
            }
         }
         for(uint32_t iK = 0; iK < K - 2; ++iK)
            for(uint32_t iN = iK; iN < N - K + iK + 1; ++iN)
               ComboCount[iK][iN] -= ComboCount[iK + 1][iN + 1];
         for(uint32_t iN = 0; iN < N - K + 1; ++iN)
            ComboCount[K - 2][iN + K - 2] -= iN;
      }
   }TheOne;

   return ComboCount;
}

// Calculate the unique ordinal for the given sorted "N-choose-K" combination.
template<uint32_t N, uint32_t K> uint32_t GetOrdinalForSortedCombination(uint32_t const combination[K])
{
   static uint32_t const(& ComboCount)[K - 1][N - 1] = GetOrdinationTable<N, K>();

   uint32_t Ordinal = 0;
   for(uint32_t i = 0; i < K - 1; ++i)
   {
      assert(combination[i] < combination[i + 1]);
      Ordinal += ComboCount[i][combination[i]];
   }
   assert(combination[K - 1] < N);
   Ordinal += combination[K - 1] - (K - 1);

   return Ordinal;
}

// Generate every combination in order and assert that their calculated ordinals are consecutive.
void TestOrdination()
{
   GetOrdinationTable<52, 7>(); // Get table setup out of the way in case we time usage.

   uint32_t combo[7];
   uint32_t NextOrdinal = 0;
   for       (combo[0] = 0;            combo[0] < 46; ++combo[0])
    for      (combo[1] = combo[0] + 1; combo[1] < 47; ++combo[1])
     for     (combo[2] = combo[1] + 1; combo[2] < 48; ++combo[2])
      for    (combo[3] = combo[2] + 1; combo[3] < 49; ++combo[3])
       for   (combo[4] = combo[3] + 1; combo[4] < 50; ++combo[4])
        for  (combo[5] = combo[4] + 1; combo[5] < 51; ++combo[5])
         for (combo[6] = combo[5] + 1; combo[6] < 52; ++combo[6])
         {
            uint32_t Ordinal = GetOrdinalForSortedCombination<52, 7>(combo);
            assert(Ordinal == NextOrdinal++);
         }
}