如何找到排列的索引 [英] How to find the index of the permutation
问题描述
% 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?
Why is it wrong? And how can I make incremention of Idx?
推荐答案
我发现了相同想法的更简洁版本，所以我展示了代码:
I found cleaner version of same idea so I show the code:
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 可以让你给它比较谓词，所以也许有用例?
This solution is not tail recursion because it seems that depth of recursion will not be a problem? It is easier to not do tail recursion, it needs less arguments. It works with any elements, only prerequisite is that elements are unique. No stupid unnecessary use of foldl or nth0/4! If you want you can additionally give it your own comparison function that only needs to be evaluated inside element_rank but this is overkill. However C++ standard library has next_permutation which lets you give it comparison predicate so maybe there is use case for this?
现在我们可以看看是否真的可以在合理的时间内找到英文字母表中所有字母的排列索引.
Now we can see if really it is possible to find the index of permutation of all letters of the English alphabet in reasonable time.
?- 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，所以也许它是正确的?您可以在下面找到原始答案，其中对算法和实现不足有一些解释.这个实现不是很好，但至少我希望它好一点?
You can see that index is exactly 26!-2 so maybe it is correct? Below you can find original answer which has some explanation of algorithm and inadequate implementation. This implementation is not good but at least it is a bit better I hope?
您真的想枚举所有可能的排列吗?在许多情况下，这可能太多了?例如，如果您有英文字母表中所有字母的排列，那么您已经有 26 个！= 一个非常大的数字(403291461126605635584000000).
You really want to enumerate all possible permutations? This is maybe too many in many of the cases? If you have a permutation of all the letters in the English alphabet for example you already have 26! = a very big number (403291461126605635584000000).
那么也许只计算而不枚举会更好?此外，我认为库 permutation/2 没有这个选项，但您应该能够按字典顺序计算下一个排列"，而无需枚举所有排列.因为当你说排列索引"时，它假设所有可能的排列都按某种顺序排列，但你没有说这是什么顺序.也许这是字典顺序?库 permutation/2 就像@CapelliC 的另一个答案一样，有一个令人讨厌的功能"，它不关心它是否真的是一个排列:
So maybe it is better to just calculate without enumerating? Also I don't think the library permutation/2 has this option but you should be able to calcuate just "next permutation" lexicographically, without enumerating all permutations. Because when you say "index of permutation" this assumes that all possible permutations are in some order, but you don't say what order this is. Maybe it is lexicographical order? And the library permutation/2 as in the other answer by @CapelliC has one annoying "feature" that it does not care if it is really a permutation or not:
?- 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?"我很不舒服这个答案.
This does not look correct to me at all. If you ask your program, "what is the index of permutation [1,1,1], should it answer "it is 1, and 2, and 3, and 4, and 5, and 6?" I am very uncomfortable with this answer.
在你开始问什么是排列的索引"之前，首先你需要问排列是如何排序的?"(按字典顺序??)并且您还需要确保列表中的所有元素实际上都是唯一的，并且它们也有顺序.我假设如果你有长度为 n 的列表，那么在这个列表中你有 1 到 n 之间的所有整数，就像你的例子一样！！！如果您有其他元素(如字母)，则必须确保它们是唯一的并且可以排序，然后您可以为它们分配 1 到 n 之间的数字，但我认为这是微不足道的，所以我不不想为它编写代码.但它可以是这样的:
Before you begin asking "what is the index of permutaton" first you need to ask "how are permutations ordered?" (lexicographically??) and you also need to make sure that all elements of your list are actually unique, and that they have an order, too. I will assume that if you have list of length n then in this list you have all integers between 1 and n, as in your example!!! If you have other elements (like letters) than you must make sure that they are unique and can be ordered and then you can assign them numbers between 1 and n but I think this is trivial so I don't want to write code for it. But it can look like this:
?- list_indices_len([c,b,a,x], Ns, Is, Len).
Ns = [3, 2, 1, 4],
Is = [1, 2, 3, 4],
Len = 4.
你明白为什么吗?如果不是，我可以解释为什么这很重要.
Do you see why? If not I can explain why this is important.
然后，一旦你有一个像 [4,1,3,2] 这样的列表及其长度，你就可以使用以下算法:
Then once you have a list like [4,1,3,2] and its length then you can use following algorithm:
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 开始的索引乘以剩余数字数量的阶乘.
This already knows the length of the permutation and the list because we made it with list_indices_len/4. Then now we only have to do n-1 steps and each time we multiply the 0-based index of the number in the list of remaining numbers with the factorial of the number of remaining numbers.
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).
一定有更好的方法来计算阶乘，但这有效吗?
There must be better way to calculate factorial but this works?
所以现在我得到了预期:
So now I get as expected:
?- 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.
The last one is exactly 10!-2 as expected.
如果你需要更多解释，我可以做，但如果你能理解逻辑，它看起来很容易理解.或者也许我的逻辑错了?不过，它似乎有效.
If you need more explaining I can do it but it looks quite easy to understand if you can understand the logic. Or maybe I am wrong about the logic? It seems to work however.
我自己做了测试，看看我对我的方法的复杂性没有感到困惑，所以我用更大的数字再次测试，结果看起来是正确的.
I made test myself to see that I am not confused about the complexity of my approach so I test again with even bigger number and it looks correct.
?- 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.
还有更有效的方法来计算排列指数，但也许您应该先阅读……您可以从头开始:
There are also even more efficient ways to calculate index of permutation but maybe you should read first... you can start at the beginning:
https://en.wikipedia.org/wiki/Permutation#Permutations_in_computing
这篇关于如何找到排列的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
