哈希

引言 在计算机科学中，哈希函数被广泛应用于各种场景，如数据结构、数据库和密码学等。在这篇文章中，我们将探讨一种特殊的哈希函数，它可以对组合问题进行连续性编号。这种哈希函数的应用场景包括但不限于：解决算法问题、优化存储空间等。 对于排列数的编号和排序问题，我们可以使用康托展开。康托展开是一种把无限维的点映射到一维的方法，它可以将一个全排列映射到一个自然数，从而实现了对数据的唯一标识。 例如对于 $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$ 个组合，我们可以将其表示为...