algorithm - 为一组整数生成 id

Question

背景:

我正在处理整数序列 {0, 1, 2 ... , n} 的排列。我有一个局部搜索算法，它以某种系统的方式将一个排列转换为另一个排列。该算法的要点是产生最小化成本函数的排列。我想处理范围广泛的问题，从 n=5 到 n=400。

问题:

为了减少搜索工作量，我需要能够检查我之前是否处理过特定的整数排列。我为此使用了哈希表，我需要能够为每个排列生成一个 id，我可以将其用作表中的键。但是，我想不出有什么好的散列函数可以将一组整数映射到一个键中，从而不会过于频繁地发生冲突。

我尝试过的东西:

我首先生成一个由 n 个质数组成的序列，然后将排列中的第 i 个数与第 i 个质数相乘，然后对结果求和。然而，即使对于 n=5，生成的 key 也会产生冲突。

我还想将所有数字的值连接在一起，并将结果字符串的整数值作为键，但即使对于较小的 n 值，id 也会很快变得太大。理想情况下，我希望能够将每个键存储为一个整数。

stackoverflow 对我有什么建议吗？

Answer 1

Zobrist hashing可能对你有用。您需要创建一个由随机整数组成的 NxN 矩阵，每个单元格表示该元素 i 在当前排列中位于第 j 个位置。对于给定的排列，您选择 N 个单元格值，然后将它们一一异或以获得排列的键(请注意，不保证键的唯一性)。

此算法的要点是，如果您交换排列中的元素，您可以通过简单地对旧位置进行异或运算并在新位置进行异或运算，轻松地从当前排列生成新 key 。