组合编码保序最小完美哈希函数逆运算如何实现优于O(K*lg N)复杂度

我正尝试为当前组合数学问题找到比现有方案更高效的解法。

假设存在包含N个对象的集合，索引范围为0..N-1，需要处理所有大小为K的子集（0≤K≤N），这类子集总数为S=C(N,K)（即组合数“N选K”）。我希望将每个此类子集映射（或称“编码”）为0..S-1范围内的唯一整数。

以N=7（索引范围0..6）、K=4（S=35）为例，期望的映射规则如下：

0 1 2 3 --> 0
0 1 2 4 --> 1
...
2 4 5 6 --> 33
3 4 5 6 --> 34

此处选择小数值的N和K仅作演示，实际应用场景中C(N,K)数值极大，无法通过 lookup table 预存映射关系，必须实时计算结果。

下文代码中combinations_table是预计算的二维数组，用于快速查询C(N,K)组合数取值。所有给出的代码均符合C++14标准。

现有编码实现 #

如果子集内的对象已按索引升序排列，可通过以下代码完成子集编码：

template<typename T, typename T::value_type N1, typename T::value_type K1>
typename T::value_type combination_encoder_t<T, N1, K1>::encode(const T &indexes)
{
   auto offset{combinations_table[N1][K1] - combinations_table[N1 - indexes[0]][K1]};

   for (typename T::value_type index{1}; index < K1; ++index)
   {
      auto offset_due_to_current_index{
           combinations_table[N1 - (indexes[index-1] + 1)][K1 - index] - 
           combinations_table[N1 - indexes[index]][K1 - index]
                                      };

      offset += offset_due_to_current_index;
   }

   return offset;
}

此处模板参数T为存储待编码索引集合的std::array<>或std::vector<>类型。

上述编码逻辑本质上是保序最小完美哈希函数（order-preserving minimal perfect hash function），我的业务场景中编码时子集内对象已经天然有序，不需要额外排序耗时，因此上述编码算法总时间复杂度为O(K)，即复杂度随K线性增长，与N无关，运行表现正常。

待优化的解码实现 #

当前核心需求是实现该函数的逆运算（即“解码”：将编码后的整数值反向还原为对应的对象索引集合）。我目前没有找到线性时间复杂度的解码方案，没有采用O(K)复杂度的直接计算方式得到对应索引，而是通过对索引空间进行二分查找实现解码，最坏时间复杂度为O(K*lg N)，对应的代码如下：

template<typename T, typename T::value_type N1, typename T::value_type K1>
void combination_encoder_t<T, N1, K1>::decode(const typename T::value_type encoded_value, T &indexes)
{
   typename T::value_type offset{0};
   typename T::value_type previous_index_selection{0};

   for (typename T::value_type index{0}; index < K1; ++index)
   {
      auto lowest_possible{index > 0 ? previous_index_selection + 1 : 0};
      auto highest_possible{N1 - K1 + index};

      // Find the *highest* ith index value whose offset increase gives a
      // total offset less than or equal to the value we're decoding.
      while (true)
      {
         auto candidate{(highest_possible + lowest_possible) / 2};

         auto offset_increase_due_to_candidate{
                   index > 0 ?
                      combinations_table[N1 - (indexes[index-1] + 1)][K1 - index] - 
                      combinations_table[N1 - candidate][K1 - index]
                             :
                      combinations_table[N1][K1] - 
                      combinations_table[N1 - candidate][K1]
                                              };

         if ((offset + offset_increase_due_to_candidate) > encoded_value)
         {
            // candidate is *not* the solution
            highest_possible = candidate - 1;
            continue;
         }

         // candidate *could* be the solution. Check if it is by checking if candidate + 1
         // could be the solution. That would rule out candidate being the solution.
         auto next_candidate{candidate + 1};

         auto offset_increase_due_to_next_candidate{
                   index > 0 ?
                      combinations_table[N1 - (indexes[index-1] + 1)][K1 - index] - 
                      combinations_table[N1 - next_candidate][K1 - index]
                             :
                      combinations_table[N1][K1] - 
                      combinations_table[N1 - next_candidate][K1]
                                                   };

         if ((offset + offset_increase_due_to_next_candidate) <= encoded_value)
         {
            // candidate is *not* the solution
            lowest_possible = next_candidate;
            continue;
         }

         // candidate *is* the solution
         offset += offset_increase_due_to_candidate;
         indexes[index] = candidate;
         previous_index_selection = candidate;
         break;
      }
   }
}

优化需求方向 #

• 算法层面优化：实现优于现有O(K*lg N)的时间复杂度，理想情况下可实现与编码过程相同的O(K)线性时间复杂度；
• 代码层面优化：在现有算法基础上提升执行速度，降低O(K*lg N)复杂度中的隐藏常数因子。

内容的提问来源于stack exchange，提问作者Dave