% 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.
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或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！=一个非常大的数字（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.
?- 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.
?- 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
fact(X,F) :- (X>0 -> Y is X-1, fact(Y,G), F is X*G ; F = 1).）将会给OP（我假设他是Prolog初学者）带来很大的困难。此外，消化Lehmer的代码和与索引的关系也不容易。 - CapelliCpermutation/2 会在回溯时生成元素。要跟踪解决方案的索引并不容易，因此这是解决您目前问题的更简单的方法：
?- findall(P,permutation([1,2,3,4],P),L), nth0(I,L,[4,1,3,2]). L = [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3|...], [2, 1|...], [2|...], [...|...]|...],
I = 19 ;
false.
编辑
如果想要更高效的做法，可以使用这个方法。
nthsol(Goal, N) :-
State = state(0, _),
Goal,
arg(1, State, C),
N is C+1,
nb_setarg(1, State, N).
?- nthsol(permutation([1,2,3,4],P),I),P=[4,1,3,2].
P = [4, 1, 3, 2],
I = 20 ;
false.
现在的索引是一个计数器，因此它会被偏移1。
call_nth/2？ - false