这个问题有两个部分,尽管我正在尝试编写一个Prolog实现,但解决其中一个问题可能会立即导致另一个问题的解决。
1. 给定整数列表的排列{1,2,...,N},如何判断该排列在词典序中的索引? 2. 给定数字k,如何计算数字{1,2...,N}的第k个排列?
我正在寻找一种比仅迭代“下一个排列”函数k次更好的算法。据我所知,应该可以直接计算这两个问题。
到目前为止,我想出来的方法是从左边看数字,在特定索引处告诉我之前有多少个排列,然后以某种方式将它们组合起来,但我不确定这是否会导致正确的解决方案。
1. 给定整数列表的排列{1,2,...,N},如何判断该排列在词典序中的索引? 2. 给定数字k,如何计算数字{1,2...,N}的第k个排列?
我正在寻找一种比仅迭代“下一个排列”函数k次更好的算法。据我所知,应该可以直接计算这两个问题。
到目前为止,我想出来的方法是从左边看数字,在特定索引处告诉我之前有多少个排列,然后以某种方式将它们组合起来,但我不确定这是否会导致正确的解决方案。