有效地存储8个不同数字和8个零的所有排列

Question

我正在为Loyd的15个难题设计一个最优的解决方案，我发现了一种使用7-8不相交模式数据库的技术(Korf，Richard E.和Felner，Ariel 2001，分离模式数据库启发式算法，人工智能，2002年1月)。

描述该技术的文章指出，每个条目，包括一个修改后的拼图的唯一状态和一个短整数启发式，需要一个字节或更少的字节才能存储在数据库中。

这就引出了我的问题:我如何在16个可能的位置存储每一个8位数的唯一排列，并将一个短整数全部存储在一个字节内？或者我是不是走错了轨道，应该储存一些不同的东西？

提前谢谢你！

Answer 1

根据洋泾孔原理，你显然走错了轨道.

洋娃娃洞原理说，如果不在一个洞里放多个果子，你就不能把更多的果子放入洞里。(也有一个无限版本，在有限数量的洞中，无限数量的pidgins意味着一个洞与无限数量的pidgins一起结束。)

在这种情况下，有518918400个独特的排列，8个数字在16个可能的地方。一个字节只能存储256个唯一的东西。不会合身的。

您需要以某种方式存储更少的信息或欺骗其存储方式。例如，您可以存储一个4GB地址的数组。只需读取数组元素在基数16中的位置，以获得它用于什么排列，数组元素的内容将告诉您与该置换相关的信息。