为一组整数生成id

Question

背景:

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

问题:

为了减少搜索工作,我需要能够检查我之前是否处理过特定的整数排列.我正在使用哈希表,我需要能够为每个排列生成一个id,我可以将其用作表中的键.但是,我想不出任何好的哈希函数将一组整数映射到一个键中,这样碰撞不会太频繁发生.

我试过的东西:

我开始生成一个n个素数序列,并将我的排列中的第i个数乘以第i个素数,然后对结果求和.然而,即使对于n = 5,所得到的密钥也会产生冲突.

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

stackoverflow对我有什么建议吗？

Answer 1

Zobrist哈希可能适合你.您需要创建一个随机整数的NxN矩阵,每个单元表示该元素i位于当前排列的第j个位置.对于给定的排列,您可以选择N个单元格值,并逐个xor来获取排列的关键字(请注意,不保证密钥唯一性).

这个算法的要点是,如果你交换到排列中的元素,你可以通过简单地排除新位置中的旧和xor-ing来轻松地从当前排列生成新密钥.

Answer 2

从您的问题和您留下的评论来判断,我会说您的问题无法解决.

让我解释.

你说你需要一个独特的哈希组合,所以让我们制定规则#1:

• 1:需要一个唯一的数字来表示任意数量的数字/数字的组合

好的,然后在评论中你已经说过,因为你使用了很多数字,由于内存的限制,将它们存储为字符串或诸如哈希表的关键字是不可行的.所以让我们将其重写为另一条规则:

• 2:无法使用用于生成哈希的实际数据,因为它们不再存在于内存中

基本上,你试图占用大量数据,并将其存储在一个小得多的数字范围内,并且仍然具有唯一性.

对不起,但你做不到.

典型的散列算法产生相对独特的散列值,所以除非你愿意接受碰撞,否则新组合可能被标记为"已经看到",即使它没有,那么你运气不好.

如果你要尝试一个位字段,每个组合都有一个位,如果没有看到它就是0,你仍然需要大量的内存.

对于你在评论中留下的n = 20的排列,你有20个!(2,432,902,008,176,640,000)组合,如果您尝试将每个组合简单地存储为位字段中的1位,则需要276,589TB的存储空间.

你将不得不限制你想要做的事情的范围.