哈希有序排列的最佳方法[1,9]

我正在尝试实现一种方法来保持8个谜题的访问状态不再生成.
我最初的方法是将每个访问过的模式保存在列表中,并在每次算法想要生成子项时进行线性检查.
现在我希望O(1)通过列表访问及时完成此操作.8拼图中的每个模式是1到9之间的数字的有序排列(9是空白块),例如125346987是:

1 2 5
3 4 6
_ 8 7

这种可能排列的数量大约为363,000(9!).将这些数字散列到该大小列表的索引的最佳方法是什么？

1> Paul Hankin..：

---

您可以将N个项目的排列映射到N个项目的所有排列列表中的索引(按字典顺序排列).

下面是一些执行此操作的代码,并演示了它为4个字母序列的所有排列生成索引0到23.

import itertools

def fact(n):
    r = 1
    for i in xrange(n):
        r *= i + 1
    return r

def I(perm):
    if len(perm) == 1:
        return 0
    return sum(p < perm[0] for p in perm) * fact(len(perm) - 1) + I(perm[1:])

for p in itertools.permutations('abcd'):
    print p, I(p)

理解代码的最佳方法是证明其正确性.对于长度为n的数组,有(n-1)!首先出现阵列最小元素的排列,(n-1)!首先出现第二个最小元素的排列,依此类推.

因此,要查找给定排列的索引,请参阅计算有多少项小于排列中的第一项并将其乘以(n-1)!. 然后递归地添加置换的其余部分的索引,被认为是(n-1)个元素的置换.基本情况是当你有一个长度为1的排列时.显然只有一个这样的排列,所以它的索引是0.

一个有效的例子:[1324].

[1324]:1首先出现,这是数组中最小的元素,因此给出0*(3!)

删除1给了我们[324].第一个元素是3.有一个元素更小,所以给我们1*(2!).

删除3给了我们[24].第一个元素是2.这是剩下的最小元素,所以它给我们0*(1!).

删除2给了我们[4].只有一个元素,所以我们使用基本情况得到0.

加起来,我们得到0*3!+ 1*2!+ 0*1!+ 0 = 1*2!= 2.因此[1324],在4个排列的排序列表中的索引2处.这是正确的,因为在索引0处[1234],索引1是[1243],并且按字典顺序排列的下一个排列是我们的[1324].

---

@Amen [排名/ unranking](https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA449&lpg=PA449&dq=ranking+unranking&source=bl&ots=z8aDQXGP3j&sig=FSnL9rrgSHFllFZrNgB_7pqxDT0&hl=en&sa=X&ved=0ahUKEwjFyIWF4InKAhUGbR4KHQ7VD2M4ChDoAQgbMAA#v=onepage&q=ranking% 20unranking&F =假)