我找到了一个更简洁的版本,以下是代码:
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) ).
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和
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)).
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