这是一个面试问题.让按字典顺序列出排列.例如123,132,213,231,312,321.给定排列在这样的列表中找到它的索引.例如,置换索引213是2(如果我们从0开始).
平凡地说,我们可以使用next_permutation算法以字典顺序生成下一个排列,但它导致O(N!)解,这显然是不可行的.有没有更好的解决方案？
我正在尝试实现一种方法来保持8个谜题的访问状态不再生成.
我最初的方法是将每个访问过的模式保存在列表中,并在每次算法想要生成子项时进行线性检查.
现在我希望O(1)通过列表访问及时完成此操作.8拼图中的每个模式是1到9之间的数字的有序排列(9是空白块),例如125346987是:
1 2 5
3 4 6
_ 8 7
这种可能排列的数量大约为363,000(9!).将这些数字散列到该大小列表的索引的最佳方法是什么？