Muf*_*ffy 3 permutation prolog
% index(+List, -Idx) Predicate will get List with permutation and I want to
know index of permutation
For example: ?- index([4,1,3,2],X).
X= 19.
我的解决方案：
index([],0).
index([_],1).
index([X,Y],2):- Y > X.
index([H,X|T],Idx):-index([X|T],Idx+1),H > X.
为什么错了？我怎样才能增加Idx？
小智 5
我找到了相同想法的更清晰版本，所以我展示了代码：
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
).
这个解决方案不是尾递归，因为看起来递归深度不会有问题？不进行尾递归更容易，它需要的参数更少。它适用于任何元素，唯一的前提是元素是唯一的。不要愚蠢地不必要地使用foldlor 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有这个选项，但您应该能够按字典顺序计算“下一个排列”，而无需枚举所有排列。因为当您说“排列索引”时，它假设所有可能的排列都按某种顺序排列，但您没有说明这是什么顺序。也许这是字典顺序？@CapelliC 的另一个答案中的库permutation/2有一个恼人的“功能”，它不关心它是否真的是一个排列：
?- 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 和n之间的所有整数，如您的示例所示！如果您有其他元素（例如字母），那么您必须确保它们是唯一的并且可以排序，然后您可以为它们分配 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