引言

在计算机科学中，哈希函数被广泛应用于各种场景，如数据结构、数据库和密码学等。在这篇文章中，我们将探讨一种特殊的哈希函数，它可以对组合问题进行连续性编号。这种哈希函数的应用场景包括但不限于：解决算法问题、优化存储空间等。

对于排列数的编号和排序问题，我们可以使用康托展开。康托展开是一种把无限维的点映射到一维的方法，它可以将一个全排列映射到一个自然数，从而实现了对数据的唯一标识。

例如对于 $1,2,3,4,5,6$ 这六个数字的全排列共 $A_6^6=720$ 个，我们可以从小到大对它们进行排序并编号：

$$ 123456 \rightarrow 0 \\ 123465 \rightarrow 1 \\ 123546 \rightarrow 2 \\ … $$

这样，我们就可以通过 $0,1,2,…,719$ 这720个数字来唯一标识这 $A_6^6$ 个排列。

然而，对于组合数的问题，例如对于六个元素中挑选三个的 $C_6^3=20$ 个组合数，我们无法通过上述方法进行排序和编号。

下面我们将尝试探究一种新的哈希函数，它可以对 $C_X^N$ 的组合数进行连续性编号。

问题呈现

我对该问题的研究起初源自于HDU 1401 “Solitaire"算法题：

HDU 1401 Solitaire
时间限制：1000ms | 内存限制：65536kB
题目描述：
给定一个8×8的棋盘，存在四颗相同棋子。每个棋子可以跳向上下左右四个方向的格子。如果格子上有棋子，可以跳过该棋子（最多跳一个），并且保证不跳出边界。给出两个状态，每个状态包含四个棋子的坐标。问在4步之内能否从第一个状态到达第二个状态。

对此问题，在进行广度优先搜索时，我们便可以使用哈希函数对棋盘状态进行编号，从而实现对状态是否已经查询的快速判断。

一个最直观也最常规的解决方案是将四颗棋子的坐标合并为一个八位数作为棋盘状态的唯一标识。

例如，对于棋盘状态 $13245768$，我们可以将其解释为 $(1,3)$ $(2,4)$ $(5,7)$ $(3,6)$ 这四个棋子的坐标。

但我们今天要讨论的是连续性编号问题，对于总共 $C_{64}^4=635376$ 个棋盘状态，我们该如何将其与 $0,1,2…,635375$ 这635376个数字一一对应呢？

下面我给出了两种思路进行方案推导和问题解决。

解决方案

我们首先定义一下该哈希函数的参数和返回值：传入一个bool[]序列seq （后文将对此详细说明），返回一个long long整数编号。其中，seq中"1"的序列和个数 $N$ 就决定了该seq在组合数 $C_X^N$ 中的位置编号。C++定义如下

long long hash_seq(bool seq[], int len) // 静态数组传入
long long hash_seq(vector<bool> seq)    // 动态数组传入

实现思路

我们可以将 $C_X^N$ 中的任意一项组合方式定义为一个二进制序列。例如对于 $C_6^3=20$ 个组合，我们可以将其表示为

$$ 000111 \rightarrow 0 \\ 001011 \rightarrow 1 \\ 001101 \rightarrow 2 \\ … \\ 111000 \rightarrow 19 $$

这样我们就实现了组合数的连续性编号。

公式推导

对于 $C_X^N$ 中的任意一项组合方式的序列，我们又该如何将其转换成一个整数编号呢？

我们先把上述的20种情况列出来

$$ 000111 \rightarrow 0 \ \ \ \ \ \ \ \ 100011 \rightarrow 10 \\ 001011 \rightarrow 1 \ \ \ \ \ \ \ \ 100101 \rightarrow 11 \\ 001101 \rightarrow 2 \ \ \ \ \ \ \ \ 100110 \rightarrow 12 \\ 001110 \rightarrow 3 \ \ \ \ \ \ \ \ 101001 \rightarrow 13 \\ 010011 \rightarrow 4 \ \ \ \ \ \ \ \ 101010 \rightarrow 14 \\ 010101 \rightarrow 5 \ \ \ \ \ \ \ \ 101100 \rightarrow 15 \\ 010110 \rightarrow 6 \ \ \ \ \ \ \ \ 110001 \rightarrow 16 \\ 011001 \rightarrow 7 \ \ \ \ \ \ \ \ 110010 \rightarrow 17 \\ 011010 \rightarrow 8 \ \ \ \ \ \ \ \ 110100 \rightarrow 18 \\ 011100 \rightarrow 9 \ \ \ \ \ \ \ \ 111000 \rightarrow 19 $$

不难发现序列编号即为该序列前的序列数量。

将其按第一个1的位置进行分组，可以发现第 $k$ 组的个数正好为（$n$为1的个数）

$$ C_{n-1+(k-1)}^{n-1}=C_{k+n-2}^{n-1} $$

原因也不难理解：

  • 当第一个1的位置固定后，剩余的1的数量为 $n-1$
  • 剩余的1将在第一个1的后续位置中进行全组合
  • 因此该组的序列数量应当为 $C_{n-1+(k-1)}^{n-1}$

我们尝试对单个位置的1进行其所在组的之前的序列个数进行求和，可以得到以下表达式（$S_n$为从右数第$n$个1的所在位）

$$ \sum_{k=1}^{S_n-n}C_{k+n-2}^{n-1} $$

再者，我们对每个位置的1按上述方式求和后的值再进行求和，不就可以得到 $C_X^N$ 中的任意一项组合方式的序列编号了吗？

$$ \sum_{n=1}^N\sum_{k=1}^{S_n-n}C_{k+n-2}^{n-1} $$

大功告成！

……了吗？

实际上，我们还可以化简一下。我们知道

$$ C_{n+1}^m=C_n^m+C_n^{m-1} $$

那对于刚才的求和，我们可以进行裂项处理

$$ \sum_{k=1}^{S_n-n}C_{k+n-2}^{n-1} \\ \begin{aligned} &=\sum_{k=1}^{S_n-n}C_{k+n-1}^n-\sum_{k=1}^{S_n-n}C_{k+n-2}^n \\ &=C_{S_n-1}^n-C_{n-1}^n \end{aligned} $$

注意到 $C_{n-1}^n$ 无意义，将其舍去可得到

$$ \sum_{k=1}^{S_n-n}C_{k+n-2}^{n-1}=C_{S_n-1}^n $$

那么原来那个复杂的双求和表达式就可以化简为

$$ \sum_{n=1}^NC_{S_n-1}^n $$

代码实现

综合上述公式，我们可以得到代码实现

long long hash_seq(bool seq[], int len) {
    int n = 0, v = 0, s[len];
    for (int i = len - 1; i >= 0; --i)
        if(seq[i]) s[++n] = v = len - i;

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += math_C(s[i] - 1, i);
    }

    return ans;
}

当然，我们也可以使用动态数组来避免传入第二个参数

#include <vector>
namespace std;

long long hash_seq(vector<bool> seq) {
    int len = seq.size();
    int n = 0, v = 0, s[len];
    for (int i = len - 1; i >= 0; --i)
        if(seq[i]) s[++n] = v = len - i;

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += math_C(s[i] - 1, i);
    }

    return ans;
}

此处math_C可以参考 组合数计算的简单实现

优化

我们发现，传入的序列中若1的数量大于0的数量，进行计算时可以利用组合数的性质 $C_n^m=C_n^{n-m}$ 进行简化运算：

  • 对seq中第一个1及其后面的位进行取反
  • 对取反后的seq进行编号计算
  • 用seq长度获取seq的最大编号
  • 使用最大编号减去取反后的seq的编号

下面是具体实现

long long hash_seq(bool seq[], int len) {
    long long flip = 0;
    int n = 0, v = 0, s[len];
    for (int i = len - 1; i >= 0; --i)
        if (seq[i]) s[++n] = v = len - i;

    if (n > v / 2) {
        flip = math_C(v, n);
        n = v = 0;
        memset(s, 0, sizeof(s));
        for (int i = len - 1; i >= 0; --i)
            if (!seq[i]) s[++n] = v = len - i;
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += math_C(s[i] - 1, i);
    }

    return flip ? flip - ans : ans;
}

其对应的动态数组版本为

#include <vector>
#include <cstring>
namespace std;

long long hash_seq(vector<bool> seq) {
    int len = seq.size();
    long long flip = 0;
    int n = 0, v = 0, s[len];
    for (int i = len - 1; i >= 0; --i)
        if (seq[i]) s[++n] = v = len - i;

    if (n > v / 2) {
        flip = math_C(v, n);
        n = v = 0;
        memset(s, 0, sizeof(s));
        for (int i = len - 1; i >= 0; --i)
            if (!seq[i]) s[++n] = v = len - i;
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += math_C(s[i] - 1, i);
    }

    return flip ? flip - ans : ans;
}

总结

在这篇文章中，我们探讨了一种特殊的哈希函数，它可以对组合问题进行连续性编号。我们提出了解决方案并进行了优化。希望这篇文章能对读者有所启发，帮助你们在实际问题中更好地应用哈希函数！