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