title: Lexicographic Rank of a Set Partitioned Into Groups
body: <p>Given a set of 8 sequential numbers <code>{0..7}</code> partitioned into 4 groups of size 2, with the numbers in each group in ascending order, how can a rank be generated for the set?  The rank should be in lexicographic order, and preferably the algorithm should be linear in complexity.</p>
  <p>Examples of the partitioning:</p>
  <pre><code>{{0 1} {2 3} {4 5} {6 7}} // Rank 0
  ...
  {{6 7} {4 5} {2 3} {0 1}} // Rank 2519
  </code></pre>
  <p>Because the numbers in each group are in ascending order, the groups are effectively treated like combinations, not permutations, so a group containing e.g. <code>{5 4}</code> will never occur.</p>
  <p>How can this set of numbers be ranked sequentially in the range <code>[0, 2520)</code> (<code>8C2 * 6C2 * 4C2</code>)?</p>
  <p>At present I compute the rank of each group as an 8C2 combination, then combine each rank together by treating it as a base-28 number.  This obviously leaves gaps in the ranking, which is undesirable in my case.  But, for what it's worth, here is how I'm currently ranking.</p>
  <pre><code>#include &lt;array&gt;
  using std::array;
  #include &lt;cstdint&gt;
  #include &lt;cstddef&gt;
  #include &lt;iostream&gt;
  using std::cout;
  using std::endl;
  
  // Calculates n!.
  uint32_t factorial(uint32_t n)
  {
    return n &lt;= 1 ? 1 : n * factorial(n - 1);
  }
  
  // Calculate nCk: n!/((n-k)!*k!).
  uint32_t choose(uint32_t n, uint32_t k)
  {
    return (n &lt; k)
      ? 0
      : factorial(n) / (factorial(n - k) * factorial(k));
  }
  
  template&lt;size_t N, size_t K&gt;
  class CombinationRanker
  {
    array&lt;array&lt;uint32_t, K+1&gt;, N+1&gt; choices;
  
  public:
    /**
     * Initialize a precomputed array of nCk (N and K inclusive).
     */
    CombinationRanker()
    {
      for (unsigned n = 0; n &lt;= N; ++n)
        for (unsigned k = 0; k &lt;= K; ++k)
          this-&gt;choices[n][k] = choose(n, k);
    }
  
    /**
     * Get the rank of a combination.
     * @param comb A combination array of size K in ascending order.
     */
    uint32_t rank(const array&lt;uint8_t, K&gt; comb) const
    {
      // Formula: (nCk) - ((n-c_1)Ck) - ((n-c_2)C(k-1)) - ... - ((n-c_k)C1)
      // That assumes 1-based combinations with ranks starting at 1, so each
      // element in the combination has 1 added to it, and the end result has 1
      // subtracted from it to make the rank 0-based.
      uint32_t rank = this-&gt;choices[N][K];
  
      for (unsigned i = 0; i &lt; K; ++i)
        rank -= this-&gt;choices[N - (comb[i] + 1)][K - i];
  
      return rank - 1;
    }
  };
  
  int main(int argc, char* argv[])
  {
    CombinationRanker&lt;8, 2&gt; ranker;
  
    array&lt;array&lt;uint8_t, 2&gt;, 4&gt; nums =
    {{
      {0, 1}, {2, 3}, {4, 5}, {6, 7}
    }};
  
    // Horribly sparse rank.
    unsigned rank =
      ranker.rank(nums[0]) * 28 * 28 * 28 +
      ranker.rank(nums[1]) * 28 * 28 +
      ranker.rank(nums[2]) * 28 +
      ranker.rank(nums[3]);
  
    cout &lt;&lt; rank &lt;&lt; endl; // 10835, but I want 0.
  
    return 0;
  }
  </code></pre>
  <p>I've tagged the post as C++ as that's the language I'm using; however, answers in another language are fine.  It's more of a math question, but I'm looking for an answer that I can understand as a programmer, not a mathematician, and a code snippet would be helpful in that regard.</p>