以优于 O(K*lg N) 的运行时间反转保序最小完美哈希函数

Question

我正在尝试寻找比我已经找到的解决方案更有效的组合问题解决方案。

假设我有一组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)太大，无法从查找表中获取这些映射。它们必须即时计算。

在下面的代码中，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<>包含我们希望找到其编码的索引的集合。

这本质上是一个“保序最小完美哈希函数”，可以在这里阅读： https:
//en.wikipedia.org/wiki/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;
      }
   }
}

这个可以改进吗？我正在寻找两类改进：

1. 算法改进，比 给定代码的O(K*lg N)运行时间更好；理想情况下，直接计算是可能的，给编码过程提供相同的O(K)运行时间
2. 代码改进可以更快地执行给定算法（即降低O(K*lg N)运行时间内隐藏的任何常数因子）

Answer 1

看一下组合的递归公式：

假设你有一个组合空间C(n,k)。您可以将该空间分为两个子空间：

• C(n-1,k-1)n所有组合，其中存在原始集合的第一个元素（长度为）
• C(n-1, k)其中第一个元素未预设

如果您有一个对应于 的组合的索引 X ，如果您检查是否属于任一子空间，则C(n,k)可以确定原始集合的第一个元素是否属于子集（对应于X） ：X

• X < C(n-1, k-1): 属于
• X >= C(n-1, k-1): 不属于

然后，您可以递归地应用相同的方法，C(n-1, ...)依此类推，直到找到n原始集合的所有元素的答案。

用于说明这种方法的 Python 代码：

import itertools, math

n=7
k=4
stuff = list(range(n))

# function that maps x into the corresponding combination
def rec(x, n, k, index):
  if n==0 and k == 0:
    return index

  # C(n,k) = C(n-1,k-1) + C(n-1, k)
  # C(n,0) = C(n,n) = 1
  c = math.comb(n-1, k-1) if k > 0 else 0
  if x < c:
    index.add(stuff[len(stuff)-n])
    return rec(x, n-1, k-1, index)
  else:
    return rec(x - c, n-1, k, index)

# Test:
for i,eta in enumerate(itertools.combinations(stuff, k)):
  comb = rec(i, n, k, set())
  print(f'{i} {eta} {comb}')

产生的输出：

0 (0, 1, 2, 3) {0, 1, 2, 3}
1 (0, 1, 2, 4) {0, 1, 2, 4}
2 (0, 1, 2, 5) {0, 1, 2, 5}
3 (0, 1, 2, 6) {0, 1, 2, 6}
4 (0, 1, 3, 4) {0, 1, 3, 4}
5 (0, 1, 3, 5) {0, 1, 3, 5}
...
33 (2, 4, 5, 6) {2, 4, 5, 6}
34 (3, 4, 5, 6) {3, 4, 5, 6}

这种方法是O(n)（虽然你的方法似乎是O( k * log(n) )(?) ），并且如果迭代重写，它应该具有相当小的常数。我不确定它是否会带来改进（需要测试）。

k我还想知道你的典型和n价值观有多大？我认为它们应该足够小，以便 C(n,k) 仍然适合 64 位？

当然，您可以使用预计算表代替math.comb，用迭代代替递归（这是尾递归，因此不需要堆栈），并使用数组代替结果集。