在优于 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) 太大而无法通过查找 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<> 保存我们希望找到其编码的索引集合。

这本质上是一个“保序最小完美哈希函数”，可以在这里阅读：
https://en.wikipedia.org/wiki/Perfect_hash_function

在我的应用程序中，子集中的对象在编码时已经自然排序，因此我不会增加排序操作的 运行 时间。因此，我的编码总 运行 时间是上面给出的算法的时间，它有 O(K) 运行 时间（即线性 K 且不依赖于 N).

上面的代码工作正常。有趣的部分是尝试反转此函数（即，将编码值“解码”回生成它的对象索引）。

对于解码，我想不出线性 运行 时间的解决方案。

我没有直接计算与编码值对应的索引（即 O(K)），而是对索引 space 找到他们。这导致 运行 时间（不比我们称之为）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

看看 recursive formula for combinations:

---

假设您有一个组合 space C(n,k)。您可以将 space 分成两个子 space：

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

如果你有一个索引 X 对应于 C(n,k) 的组合，你可以识别你的原始集合的第一个元素是否属于子集（对应于 X），如果你检查 X 是否属于 subspace:

• 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，用迭代代替递归（是尾递归，不需要栈），结果用数组代替集合。

Answer 2

为了将来参考，我想添加 @aivean 给出的算法改进的 C++ 实现（事实证明它非常有效），用于将编码值解码回生成它的索引。

与原来的post一样，combinations_table是一个预先计算好的二维数组，用于快速查找C(N,K)值.

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)
{
   auto n{N1};
   auto k{K1};
   auto x(encoded_value);
   T1 index{0};

   while (k != 0)
   {
      auto c{combinations_table[n-1][k-1]};

      if (x < c)
      {
         indexes[index++] = N1 - n;
         --k;
      }
      else
         x -= c;

      --n;
   }
}