prologpermutationparity

A Prolog program for permutation parity


I wrote this small program in Prolog.

odd_even_flip(odd, even).
odd_even_flip(even, odd).

% flip_one, for A = a, B = b, P = [a, .., b, ..], gives M = [b, .., a, ..]
flip_one(A, B, P, M) :-
    append([A|As], [B|Bs], P),
    append([B], As, L),
    append([A], Bs, R),
    append(L, R, M).
    
permutation_parity([X|L], [X|P], R) :- permutation_parity(L, P, R).
% abc
permutation_parity([X|L], [Y|P], R) :-
    X \= Y,
    flip_one(Y, X, [Y|P], M),
    permutation_parity([X|L], M, Res),
    odd_even_flip(Res, R).
permutation_parity([], [], even).

I expect it to find the parity of a permutation P of list L. The few queries that assert that a given permutation of a given list is indeed even or odd worked fine.

However, from my experience with Prolog, I would expect that permutation_parity([a, b, c], X, Y). would show me all permutations of [a, b, c] but that is not happening.

Rather, I get X = [a, b, c], Y = even. and that is all.

I tried to add member(Y, L) in the rule that follows %abc as I was thinking that will help Prolog to know how to instantiate X in permutation_parity([a, b, c], X, Y) but that helped to no avail.

If someone could help me see what I am missing it would be great. Thanks in advance.


Solution

  • You only need to use unification to correctly instantiate the variable X (assuming that permutation_parity/3 is called with a proper list as its first argument). So I suggest you modify your code as follows:

    permutation_parity([], [], even).
    permutation_parity([X|Xs], [X|Zs], P) :-
        permutation_parity(Xs, Zs, P).
    permutation_parity([X|Xs], Zs, P) :-
        permutation_parity(Xs, Ys, Q),
        flip_first([X|Ys], Zs),
        odd_even_flip(Q, P).
    
    flip_first(L0, L1) :-
        append([X|Xs], [Y|Ys], L0),
        append([Y|Xs], [X|Ys], L1).
    
    odd_even_flip(odd, even).
    odd_even_flip(even, odd).
    

    Examples:

    ?- permutation_parity([a,b,c], Permutation, Parity).
    Permutation = [c, a, b],
    Parity = even ;
    Permutation = [b, c, a],
    Parity = even ;
    Permutation = [b, a, c],
    Parity = odd ;
    Permutation = [c, b, a],
    Parity = odd ;
    Permutation = [a, c, b],
    Parity = odd ;
    Permutation = [a, b, c],
    Parity = even.
    
    ?- permutation_parity([a,b,c], [a,c,b], Parity).
    Parity = odd ;
    false.
    
    ?- permutation_parity([a,b,c], Permutation, even).
    Permutation = [c, a, b] ;
    Permutation = [b, c, a] ;
    Permutation = [a, b, c].
    

    EDIT

    perm_parity(L0, L1, P) :-
        same_length(L0, L1),
        permutation_parity(L0, L1, P).
    

    The predicate same_length/2 is defined in SWI-Prolog as follows:

    same_length([], []).
    same_length([_|T1], [_|T2]) :-
        same_length(T1, T2).
    

    Example:

    ?- perm_parity(L, [a,b,c], P).
    L = [b, c, a],
    P = even ;
    L = [c, a, b],
    P = even ;
    L = [b, a, c],
    P = odd ;
    L = [c, b, a],
    P = odd ;
    L = [a, c, b],
    P = odd ;
    L = [a, b, c],
    P = even.