我找到了相同想法的更清晰版本，所以我展示了代码：
permutation_index([X|Xs], I) :-
prerequisite(
( sort([X|Xs], S),
length([X|Xs], Len),
length(S, Len)
)),
permutation_index(Xs, X, _N, _N_fac, I).
prerequisite(P) :- P.
permutation_index([], _Last, 0, 1, 0).
permutation_index([X|Xs], Prev, N, N_fac, I) :-
permutation_index(Xs, X, N0, N_fac0, I0),
succ(N0, N),
N_fac is N*N_fac0,
element_rank([X|Xs], Prev, R),
I is I0 + R*N_fac.
element_rank([], _, 0).
element_rank([X|Xs], Y, R) :-
element_rank(Xs, Y, R0),
( X @< Y
-> succ(R0, R)
; R0 = R
).
这个解决方案不是尾递归，因为看起来递归深度不会有问题？不进行尾递归更容易，它需要的参数更少。它适用于任何元素，唯一的前提是元素是唯一的。没有愚蠢的不必要的使用foldl or nth0/4！如果你愿意，你还可以给它你自己的比较函数，只需要在内部进行评估element_rank但这太过分了。然而C++标准库有next_permutation它可以让你给它比较谓词，所以也许有这样的用例？
现在我们可以看看是否真的有可能在合理的时间内找到英语字母表中所有字母的排列索引。
?- bagof(C, ( char_type(C, lower), C @> b, C @=< z ), Cs),
reverse(Cs, Cs_rev),
append(Cs_rev, [a,b], Letters),
time( permutation_index(Letters, I) ).
% 1,103 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4226847 Lips)
Cs = [c, d, e, f, g, h, i, j, k|...],
Cs_rev = [z, y, x, w, v, u, t, s, r|...],
Letters = [z, y, x, w, v, u, t, s, r|...],
I = 403291461126605635583999998.
您可以看到索引正好是 26!-2 所以也许它是正确的？您可以在下面找到原始答案，其中对算法和不充分的实现进行了一些解释。这个实现不好，但至少我希望它好一点？
您真的想枚举所有可能的排列吗？在很多情况下这可能太多了？例如，如果您有英文字母表中所有字母的排列，那么您已经有 26 个了！ = 一个非常大的数字（403291461126605635584000000）。
那么也许只计算而不枚举更好？我也不认为图书馆permutation/2有此选项，但您应该能够按字典顺序计算“下一个排列”，而无需枚举所有排列。因为当您说“排列索引”时，它假设所有可能的排列都按某种顺序排列，但您没有说明这是什么顺序。也许这是字典顺序？还有图书馆permutation/2正如 @CapelliC 的另一个答案有一个令人讨厌的“功能”，它不关心它是否真的是一种排列：
?- permutation([1,1,1], P).
P = [1, 1, 1] ;
P = [1, 1, 1] ;
P = [1, 1, 1] ;
P = [1, 1, 1] ;
P = [1, 1, 1] ;
P = [1, 1, 1] ;
false.
这对我来说根本不正确。如果你问你的程序，“排列索引 [1,1,1] 是多少，它应该回答“是 1、2、3、4、5、6 吗？”我对此感到非常不舒服这个答案。
在你开始问“排列的索引是什么”之前，你首先需要问“排列是如何排序的？” （按字典顺序？？）并且您还需要确保列表中的所有元素实际上都是唯一的，并且它们也有顺序。我假设如果你有长度列表n那么在此列表中，您拥有 1 到 1 之间的所有整数n，就像你的例子一样！！！如果您有其他元素（例如字母），则必须确保它们是唯一的并且可以排序，然后您可以为它们分配 1 到 1 之间的数字n但我认为这是微不足道的，所以我不想为其编写代码。但它可以看起来像这样：
?- list_indices_len([c,b,a,x], Ns, Is, Len).
Ns = [3, 2, 1, 4],
Is = [1, 2, 3, 4],
Len = 4.
你明白为什么吗？如果不是，我可以解释为什么这很重要。
然后，一旦你有了像 [4,1,3,2] 这样的列表及其长度，那么你可以使用以下算法：
permutation_index(P, Es, Len, I) :-
succ(Len0, Len),
P = [N|Ns],
permutation_index(Ns, N, Len0, Es, 0, I).
这已经知道排列和列表的长度，因为我们用list_indices_len/4。那么现在我们只需要执行 n-1 步，每次我们将剩余数字列表中数字的从 0 开始的索引与剩余数字的阶乘相乘。
permutation_index([], _, _, _, I, I).
permutation_index([N|Ns], N0, X, Es, Acc, I) :-
once( nth0(N_i, Es, N0, Es0) ),
factorial_expr(X, X_fac),
succ(X0, X),
Acc1 is N_i*X_fac + Acc,
permutation_index(Ns, N, X0, Es0, Acc1, I).
factorial_expr(F, E) :-
( F =:= 0
-> E = 1
; F =:= 1
-> E = 1
; F > 1
-> X is F,
numlist(2, X, [N|Ns]),
foldl(prod, Ns, N, E)
).
prod(X, Y, Y*X).
一定有更好的方法来计算阶乘，但这有效吗？
所以现在我得到了预期的结果：
?- permutation_index([4,1,3,2], [1,2,3,4], 4, I).
I = 19.
?- permutation_index([4,3,2,1], [1,2,3,4], 4, I).
I = 23.
?- permutation_index([1,2,3,4], [1,2,3,4], 4, I).
I = 0.
?- permutation_index([1,2,4,3], [1,2,3,4], 4, I).
I = 1.
?- permutation_index([10,9,8,7,6,5,4,3,1,2], [1,2,3,4,5,6,7,8,9,10], 10, I).
I = 3628798.
最后一个正好是 10!-2 ，正如预期的那样。
如果您需要更多解释，我可以做，但如果您能理解逻辑，它看起来很容易理解。或者也许我的逻辑是错误的？然而它似乎有效。
我自己做了测试，看看我对我的方法的复杂性没有感到困惑，所以我用更大的数字再次测试，它看起来是正确的。
?- time(permutation_index([12,11,10,9,8,7,6,5,4,3,1,2], [1,2,3,4,5,6,7,8,9,10,11,12], 12, I)).
% 466 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 1498045 Lips)
I = 479001598.
?- factorial_expr(12, E), X is E - 2.
E = ... * ... * 4*5*6*7*8*9*10*11*12,
X = 479001598.
还有更有效的方法来计算排列索引，但也许您应该先阅读......您可以从头开始：
https://en.wikipedia.org/wiki/Permutation#Permutations_in_computing https://en.wikipedia.org/wiki/Permutation#Permutations_in_computing
