Generating the mth Lexicographical Element of a Combination Using the Combinadic

Suppose you are working with mathematical (n=5, k=3) combinations. There are Choose(5,3) = 5! / (3! * (5-3)!) = 120 / 12 = 10 different combination elements. In lexicographical order they are:

[0] 0 1 2
[1] 0 1 3
[2] 0 1 4
[3] 0 2 3
[4] 0 2 4
[5] 0 3 4
[6] 1 2 3
[7] 1 2 4
[8] 1 3 4
[9] 2 3 4

Note: I use 0-based indexing.

Several years ago I learned about a neat technique from Laci Lovasz of Microsoft Research. He suggested that the combinadic of a number can be used to generate the mth (n,k) combination. He did not use the term “combinadic” so I coined the term because the concept is similar to the factoradic of a number.

I published an article in the old Microsoft MSDN Magazine but MSDN has been vaporized into Internet ether. I summarize that old article in this blog post.

If you want just element m = [4] you could start with (0 1 2) and assuming you have a Successor() function, loop 4 times to get to (0 2 4). It turns out that writing a Successor() function for combinations is a bit tricky but feasible. However, because the number of combinations for order n and subset size k become astronomically large for even moderate sized values of n and k, the iteration approach won’t work except for small values of m. For example, if you have (n=200, k=10) there are Choose(200, 10) = 22,451,004,309,013,280 possible combination elements

It turns out that there’s a clever way to directly generate combination element [m] using an old math idea I call the combinadic. The essence of the algorithm is to take m, compute its “combinadic”, and then use that to compute the combination.

Combinadics

You can think of a combinadic as an alternate representation of an integer. Consider the integer 859. It can be represented as

859 = (8 * 100) + (5 * 10) + (9 * 1)

Or another way of looking at it is as based on a fixed radix (base) of powers of 10:

859 = (8 * 10^2) + (5 * 10^1) + (9 * 10^0)

In short, any number can be uniquely represented as a linear sum of powers of 10. The combinadic of an integer is its representation based on a variable base corresponding to the values of the Choose(n,k) function. For example if (n=7, k=4) then the integer 27 can be represented as

27 = Choose(6,4) + Choose(5,3) + Choose(2,2) + Choose(1,1)
   = 15 + 10 + 1 + 1

With (n=7, k=4), any number m between 0 and 34 (the total number of combination elements for n and k) can be uniquely represented as:

m = Choose(c1,4) + Choose(c2,3) + Choose(c3,2) + Choose(c4,1)

where n less-than c1 less-than c2 less-than c3 less-than c4. Notice that n is analogous to the base because all combinadic digits are between 0 and n-1 (just like all digits in ordinary base 10 are between 0 and 9). The k value determines the number of terms in the combinadic. The combinadic of a number can be calculated fairly quickly.

Here’s an example of how a combinadic is calculated. Suppose you are working with (n=7, k=4) combinations, and m = 8. You want the combinadic of 8 because, as it turns out, the combinadic can be converted to combination element [8].

The combinadic of 8 will have the form:

8 = Choose(c1,4) + Choose(c2,3) + Choose(c3,2) + Choose(c4,1)

The first step is to determine the value of c1. We try c1 = 6 (the largest number less than n = 7) and get Choose(6,4) = 15, which is too large because we’re over 8. Next, we try c1 = 5 and get Choose(5,4) = 5, which is less than 8, so bingo, c1 = 5.

At this point we have used up 5 of the original number m=8 so we have 3 left to account for. To determine the value of c2, we try 4 (the largest number less than the 5 we got for c1), but get Choose(4,3) = 4, which is barely too large. Working down we get to c2 = 3 and Choose(3,3) = 1, so c2 = 3.

We used up 1 of the remaining 3 we had to account for, so we have 2 left to consume. Using the same ideas we’ll get c3 = 2 with Choose(2,2) = 1, so we have 1 left to account for. And then we’ll find that c4 = 1 because Choose(1,1) = 1. Putting our four c values together we conclude that the combinadic of m=8 for (n=7, k=4) combinations is ( 5 3 2 1 ).

Duals

Before I explain how to use the combinadic of a number to determine the mth lexicographical element of a combination, I need to explain the idea of the dual of each lexicographic index. Suppose (n=7, k=4). There are Choose(7,4) = 35 combination elements, indexed from 0 to 34. The dual indexes are the ones on opposite ends so to speak: indexes 0 and 34 are duals, indexes 1 and 33 are duals, indexes 2 and 32 are duals, and so forth. Notice that each pair of dual indexes sum to 34, so if you know any index it is easy to find its dual.

Now, continuing the first example above for the number m=27 with (n=7, k=4), suppose you are able to find the combinadic of 27 and get ( 6 5 2 1 ). Now suppose you subtract each digit in the combinadic from n-1 = 6 and get ( 0 1 4 5 ). Amazingly, this gives you the combination element [7], the dual index of 27. Putting these ideas together you have an elegant algorithm to determine an arbitrarily specified combination element for given n and k values. To find the combination element for index m, first find its dual and call it x. Next, find the combinadic of x. Then subtract each digit of the combinadic of x from n-1 and the result is the mth lexicographic combination element.

The table below shows the relationships among m, the dual of m, combination element [m], the combinadic of m, and (n-1) – ci for (n=5, k=3).

m dual(m) Element(m) combinadic(m) (n-1) - ci
==============================================
[0]  9    { 0 1 2 }   ( 2 1 0 )     ( 2 3 4 )
[1]  8    { 0 1 3 }   ( 3 1 0 )     ( 1 3 4 )
[2]  7    { 0 1 4 }   ( 3 2 0 )     ( 1 2 4 )
[3]  6    { 0 2 3 }   ( 3 2 1 )     ( 1 2 3 )
[4]  5    { 0 2 4 }   ( 4 1 0 )     ( 0 3 4 )
[5]  4    { 0 3 4 }   ( 4 2 0 )     ( 0 2 4 )
[6]  3    { 1 2 3 }   ( 4 2 1 )     ( 0 2 3 )
[7]  2    { 1 2 4 }   ( 4 3 0 )     ( 0 1 4 )
[8]  1    { 1 3 4 }   ( 4 3 1 )     ( 0 1 3 )
[9]  0    { 2 3 4 }   ( 4 3 2 )     ( 0 1 2 )

Implementation

Here is C# code that implements the algorithm, where a combination is represented as an array of int values. The implementation uses the BigInteger type because Choose() results can be huge.

Replace “lt”, “gt”, “lte”, “gte” with Boolean operator symbols (my lame blog editor chokes on symbols).

using System;
using System.Numerics;

namespace Combinations // classic style template
{
  internal class CombinationsProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin combinadic demo ");

      BigInteger numCombs = Choose(100, 10);
      Console.WriteLine("Number (n=100, k=10) combinations: ");
      Console.WriteLine(numCombs.ToString("N0"));

      int n = 100;
      int k = 10;
      BigInteger m = BigInteger.Parse("9999999999");
      int[] c = Element(m, n, k);
      Console.WriteLine("\nCombination m=[" + m + "]" +
        " of C(n=100,k=10): ");
      ShowComb(c);

      Console.WriteLine("\nEnd combinadic demo \n");
      Console.ReadLine();
    } // Main

    static void ShowComb(int[] comb)
    {
      int n = comb.Length;
      for (int i = 0; i "lt" n; ++i)
        Console.Write(comb[i] + " ");
      Console.WriteLine("");
    }

    static int[] Element(BigInteger m, int n, int k)
    {
      // compute element [m] using the combinadic
      BigInteger maxM = Choose(n, k) - 1;

      if (m "gt" maxM)
        throw new Exception("m value too large in Element");

      int[] ans = new int[k];

      int a = n;
      int b = k;
      BigInteger x = maxM - m; // x is the "dual" of m

      for (int i = 0; i "lt" k; ++i)
      {
        ans[i] = LargestV(a, b, x); // see helper below    
        x = x - Choose(ans[i], b);
        a = ans[i];
        b = b - 1;
      }

      for (int i = 0; i "lt" k; ++i)
        ans[i] = (n - 1) - ans[i];

      return ans;
    }

    static int LargestV(int a, int b, BigInteger x)
    {
      // helper for Element()
      int v = a - 1;
      while (Choose(v, b) "gt" x)
        --v;
      return v;
    }

    static BigInteger Choose(int n, int k)
    {
      // number combinations
      if (n "lt" 0 || k "lt" 0)
        throw new Exception("Negative arg in Choose()");
      if (n "lt" k) return 0; // special
      if (n == k) return 1; // short-circuit

      int delta, iMax;

      if (k "lt" 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 (int i = 2; i "lte" iMax; ++i)
        ans = (ans * (delta + i)) / i;

      return ans;
    }

  } // Program

} // ns