分组的集合的词典顺序

Question

给定一组 8 个序号 {0..7}，分成 4 个大小为 2 的组，每组中的数字按升序排列，如何为该组生成排名？排名应该是字典顺序，最好算法复杂度是线性的。

分区示例：

{{0 1} {2 3} {4 5} {6 7}} // Rank 0
...
{{6 7} {4 5} {2 3} {0 1}} // Rank 2519

因为每组中的数字是按升序排列的，所以这些组实际上被视为组合，而不是排列，所以一个包含例如{5 4}永远不会发生。

这组数字如何在[0, 2520)（8C2 * 6C2 * 4C2）范围内按顺序排列？

目前我将每个组的排名计算为一个 8C2 组合，然后将每个排名组合在一起，将其视为 base-28 数字。这显然会在排名中留下差距，这对我来说是不可取的。但是，就其价值而言，这是我目前的排名。

#include <array>
using std::array;
#include <cstdint>
#include <cstddef>
#include <iostream>
using std::cout;
using std::endl;

// Calculates n!.
uint32_t factorial(uint32_t n)
{
  return n <= 1 ? 1 : n * factorial(n - 1);
}

// Calculate nCk: n!/((n-k)!*k!).
uint32_t choose(uint32_t n, uint32_t k)
{
  return (n < k)
    ? 0
    : factorial(n) / (factorial(n - k) * factorial(k));
}

template<size_t N, size_t K>
class CombinationRanker
{
  array<array<uint32_t, K+1>, N+1> choices;

public:
  /**
   * Initialize a precomputed array of nCk (N and K inclusive).
   */
  CombinationRanker()
  {
    for (unsigned n = 0; n <= N; ++n)
      for (unsigned k = 0; k <= K; ++k)
        this->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<uint8_t, K> 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->choices[N][K];

    for (unsigned i = 0; i < K; ++i)
      rank -= this->choices[N - (comb[i] + 1)][K - i];

    return rank - 1;
  }
};

int main(int argc, char* argv[])
{
  CombinationRanker<8, 2> ranker;

  array<array<uint8_t, 2>, 4> 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 << rank << endl; // 10835, but I want 0.

  return 0;
}

我已将 post 标记为 C++，因为那是我正在使用的语言；但是，用另一种语言回答也没问题。这更像是一个数学问题，但我正在寻找一个我作为程序员而不是数学家可以理解的答案，代码片段在这方面会有所帮助。

Answer 1

这是我想出的。它的复杂度是二次方的，虽然不是最复杂的，但它可以解决问题。基本算法如下

给定一组来自 [0..7] 的序列号，并将其划分为无序对，遍历每一对并找到其在满足以下条件的对中的排名排除它前面的数字。然后将每个等级乘以其变量根据。每个等级的可变基数为 6C2*4C2*2C2、4C2*2C2 和 2C2.

例如，{{2,3}, {6,7}, {4,5}, {0,1}}:

{2, 3} 排名 13。
{6, 7} 在不包括 2 和 3 的对中排名第 14。
{4, 5} 在不包括 2、3、6 和 7 的对中排名第 5。
{0, 1} 被忽略。

一共13*6C2*4C2*2C2 + 14*4C2*2C2 + 5*2C2 = 1259

其他示例：

{{0, 1}, {2, 3}, {4, 5}, {6, 7}} -> 0
{{2, 3}, {6, 7}, {4, 5}, {0, 1}} -> 1259
{{2, 4}, {0, 1}, {3, 5}, {6, 7}} -> 1260
{{6, 7}, {4, 5}, {2, 3}, {0, 1}} -> 2519

这是代码中的算法。为了简洁起见，我硬编码了很多。

#include <iostream>
using std::cout;
using std::endl;
#include <array>
using std::array;
#include <cstdint>

typedef array<uint8_t, 2> pair_t;

/**
 * @param set A set of 8 sequential numbers, [0..7], partitioned into unordered
 * pairs.
 */
uint32_t rank(const array<pair_t, 4>& set) {
  // All 28 (8C2) possible unordered subsets of the set of 8 sequential
  // numbers, [0..7], in lexicographic order.  Hard-coded here for brevity.
  array<pair_t, 28> pairs = {{
    {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7},
            {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7},
                    {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7},
                            {3, 4}, {3, 5}, {3, 6}, {3, 7},
                                    {4, 5}, {4, 6}, {4, 7},
                                            {5, 6}, {5, 7},
                                                    {6, 7},
  }};

  // Variable base for each rank "digit" (the base corresponding to the rank of
  // each subset): 6C2*4C2*2C2, 4C2*2C2, 2C2.  Again, hard-coded for brevity.
  array<uint32_t, 3> bases = {{90, 6, 1}};

  // Now rank the set.
  uint32_t rank = 0;
  // Rank among this many pairs.  For N=8, 8C2->6C2->4C2->2C2 (28->15->6->1).
  unsigned numRemaining = 28; // N*(N-1)/2
  array<pair_t, 28> remaining = pairs;

  // Loop over the first three unordered subsets.  The last isn't needed for
  // ranking--n from [0...(N-2)/2).
  for (unsigned n = 0; n < 3; ++n)
  {
    unsigned remainingInd = 0;
    const pair_t& sPair = set[n];

    for (unsigned r = 0; r < numRemaining; ++r)
    {
      const pair_t& rPair = remaining[r];

      if (sPair == rPair)
      {
        // Found the pair: rank it relative to the ramining pairs, and multiply
        // it by the base for digit n.
        rank += r * bases[n];
      }
      else if (
        sPair[0] != rPair[0] && sPair[0] != rPair[1] &&
        sPair[1] != rPair[0] && sPair[1] != rPair[1]
      )
      {
        // The pair excludes the numbers in set[n], so keep it in the
        // list of remaining pairs for the next digit's rank.
        remaining[remainingInd++] = rPair;
      }
    }

    // Number of remaining pairs.
    numRemaining = remainingInd;
  }

  return rank;
}

int main(int argc, char* argv[])
{
  // Examples pairs.
  array<array<pair_t, 4>, 7> sets = {{
    {{{0, 1}, {2, 3}, {4, 5}, {6, 7}}},
    {{{0, 1}, {2, 3}, {4, 6}, {5, 7}}},
    {{{0, 1}, {2, 3}, {4, 7}, {5, 6}}},
    {{{0, 1}, {2, 3}, {5, 6}, {4, 7}}},
    // snip
    {{{2, 3}, {6, 7}, {4, 5}, {0, 1}}},
    // snip
    {{{6, 7}, {4, 5}, {1, 3}, {0, 2}}},
    {{{6, 7}, {4, 5}, {2, 3}, {0, 1}}},
  }};

  for (unsigned i = 0; i < 7; ++i)
  {
    const array<pair_t, 4>& set = sets[i];

    cout << rank(set) << ": ";

    for (unsigned j = 0; j < 4; ++j)
      cout << '{' << (unsigned)set[j][0] << ", " << (unsigned)set[j][1] << '}';

    cout << endl;
  }

  return 0;
}

输出：

0: {0, 1}{2, 3}{4, 5}{6, 7}
1: {0, 1}{2, 3}{4, 6}{5, 7}
2: {0, 1}{2, 3}{4, 7}{5, 6}
3: {0, 1}{2, 3}{5, 6}{4, 7}
1259: {2, 3}{6, 7}{4, 5}{0, 1}
2518: {6, 7}{4, 5}{1, 3}{0, 2}
2519: {6, 7}{4, 5}{2, 3}{0, 1}

分组的集合的词典顺序

Lexicographic Rank of a Set Partitioned Into Groups

c++

combinatorics