计算序言中列表的排列 [英] Counting permutations of a list in prolog

问题描述

在Prolog 2nd Edition中存在一个问题，您应该定义一个谓词even_permutation(Xs，Ys)和类似的奇数置换，当您查询例如even_permutation([1,2,3]，[2 ，3,1])和odd_permutation([1,2,3]，[2,1,3])为真.这些谓词应能够在随机列表上工作，并确定该列表的排列是否在奇数或偶数位置.如图所示，我有用于拼写的谓词.

permutation([],[]).
permutation(Xs,[Z|Zs]):-select(Z,Xs,Ys), permutation(Ys,Zs).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):- select(X,Ys,Zs).

我有一个想法，我计算列表的排列数量并将它们分组为偶数和奇数排列，然后我的查询可以确定排列是奇数还是偶数，但是我不知道如何实现它.如果有更好的方法，请告诉我.

解决方案

以下是有关如何确定排列是偶数还是奇数的高级描述，枚举所有排列，使其仅返回相同奇偶校验的排列(请参见该部分及其后一个).

There is a question is in Art of prolog 2nd edition where you are supposed to define a predicate even_permutation(Xs,Ys) and similarly odd permutations which when you query for example even_permutation([1,2,3],[2,3,1]) and odd_permutation([1,2,3],[2,1,3]) are true.These predicates should be able to work on a random list and determine if a permutation of that list is in an odd or even position. I have my predicate for pemutation as shown.

permutation([],[]).
permutation(Xs,[Z|Zs]):-select(Z,Xs,Ys), permutation(Ys,Zs).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):- select(X,Ys,Zs).

I have an idea where i count the number of permutations of the list and group them into even and odd permutations then my query can determine whether a permutaion is odd or even but i have no idea how to implement it. If there is a better way to do it please tell me.

解决方案

Here's a high-level description of how to determine if a permutation is even or odd, in the usual sense of the terms.

Convert the permutation into a product of disjoint cycles. The parity of the permutation is the sum of parities of its factors (even times even or odd times odd is even, odd times even or even times odd is odd). A cycle of odd length is an even permutation, and a cycle of even length is an odd permutation. For example, a cycle of length one is the identity permutation and thus (expressed as the empty product of transpositions) is an even permutation.

Finding the product of disjoint cycles representation can be done in your setup by picking an item from the first list, looking up where it gets mapped by the corresponding location in the second list, and repeating this lookup with the image of each succeeding item until the cycle returns to the item at the beginning of the first list. The list of successive images will be disjoint from the orbits of items not in the list, so consider them eliminated and begin finding the next disjoint cycle with the first item of the first list that is not yet eliminated. Eventually all the items in the first list will be eliminated, having been incorporated into one or another of the constructed cycles.

Other approaches to determining the parity of a given permutation are described in the article linked above. If you really wish to enumerate only even permutations (resp. only odd permutations), one approach is to modify the enumeration of all permutations in a way that returns only permutations of the same parity (cf. that section and the one following).

这篇关于计算序言中列表的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！