Counting permutations of a list in prolog

Question

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.

Answer 1

I know the original question was posted quite some time ago, but I was very recently working through some of the problems in The Art Of Prolog as well and thought over the even/odd permutation problem for a few days. I didn't want to open a duplicate problem, so I'm posting my solution here.

The problem in the book asks:

Write programs for even_permutation(Xs, Ys) and odd_permutation(Xs, Ys) that find Ys, the even and odd permutations, respectively, of a list Xs. For example, even_permutation([1,2,3], [2,3,1]) and odd_permutation([1,2,3], [2,1,3]) are true.

So it's asking for permutation generators, not just verifiers. @hardmath has provided a link to the correct definition of even or odd permutation. The authors of the book gave two simple examples to illustrate.

For me, the key was figuring out a recursive definition for an even or odd permutation. For all permutations, the classical permutation generator in Prolog uses the following notion:

• Every permutation of N+1 elements is a list representing a permutation of N of the elements with the (N+1)st element inserted into the list.

The predicate select or insert is used to do the insertion.

For even and odd permutations, I considered a similar idea:

• Every even permutation of N+1 elements is either a list representing an even permutation of N of the elements with the (N+1)st element inserted at an odd position in the list, or a list representing an odd permutation of N of the elements with the (N+1)st element inserted at an even position in the list.

• Every odd permutation of N+1 elements is either a list representing an odd permutation of N of the elements with the (N+1)st element inserted at an odd position in the list, or a list representing an even permutation of N of the elements with the (N+1)st element inserted at an even position in the list.

The rational is that the insertion of an element at an odd position represents an even number of swaps relative to the original list (the front of the list, being the first position, requires no swaps, so it's even). Similarly, the insertion of an element at an even position represents an odd number of swaps relative to the original list.

If I add to this the rule that the empty list is it's own even permutation, then I can define the following predicates as follows to generate the even and odd permutations:

even_permutation( [], [] ).
even_permutation( [X|T], Perm ) :-
    even_permutation( T, Perm1 ),
    insert_odd( X, Perm1, Perm ).
even_permutation( [X|T], Perm ) :-
    odd_permutation( T, Perm1 ),
    insert_even( X, Perm1, Perm ).

odd_permutation( [X|T], Perm ) :-
    odd_permutation( T, Perm1 ),
    insert_odd( X, Perm1, Perm ).
odd_permutation( [X|T], Perm ) :-
    even_permutation( T, Perm1 ),
    insert_even( X, Perm1, Perm ).

insert_odd( X, InList, [X|InList] ).
insert_odd( X, [Y,Z|InList], [Y,Z|OutList] ) :-
    insert_odd( X, InList, OutList ).

insert_even( X, [Y|InList], [Y,X|InList] ).
insert_even( X, [Y,Z|InList], [Y,Z|OutList] ) :-
    insert_even( X, InList, OutList ).

Answer 2

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).