Krdytkyu

This is the exercise 3.3.1(iv) from The Art Of Prolog where it's asked to find even and odd permutations. I used Heap's algorithm which finds all permutations which always have one step from each other.

get([E|_],0,E).

get([_|T],N,E):-

    N1 is N-1,

    get(T,N1,E).



put([_|T],0,E,[E|T]).

put([H|T],N,E,[H|T2]):-

    N1 is N-1,

    put(T,N1,E,T2).



swap(L,N1,N2,R):-

    get(L,N1,E1),

    get(L,N2,E2),

    put(L,N2,E1,R1),

    put(R1,N1,E2,R).



odd(N):-

    N mod 2 =:= 1.



even(N):-

    N mod 2 =:= 0.



len(,0).

len([_|T],N):-

    len(T,N1),

    N is N1+1.



heap_loop(LI,N,CI,A,I,LO,CO,R):-

    I = 0,

    N1 is N-1,

    heap_rec(LI,N1,CI,A,L1,C1,R1),

    heap_loop(L1,N,C1,R1,1,LO,CO,R).

heap_loop(LI,N,CI,A,I,LO,CO,R):-

    I > 0,

    I < N,

    odd(N),

    N1 is N-1,

    swap(LI,1,N1,L0),

    heap_rec(L0,N1,CI,A,L1,C1,R1),

    I1 is I+1,

    heap_loop(L1,N,C1,R1,I1,LO,CO,R).

heap_loop(LI,N,CI,A,I,LO,CO,R):-

    I > 0,

    I < N,

    even(N),

    N1 is N-1,

    I1 is I-1,

    swap(LI,I1,N1,L0),

    heap_rec(L0,N1,CI,A,L1,C1,R1),

    I2 is I+1,

    heap_loop(L1,N,C1,R1,I2,LO,CO,R).

heap_loop(LI,N,CI,A,I,LO,CO,R):-

    I = N,

    CO = CI,

    LO = LI,

    R = A.



heap_rec(LI,N,CI,A,LO,CO,R):-

    N = 1,

    R = [perm(CI,LI)|A],

    CO is CI+1,

    LO=LI.

heap_rec(LI,N,CI,A,LO,CO,R):-

    N > 1,

    heap_loop(LI,N,CI,A,0,LO,CO,R).



heap(L,R):-

    len(L,N),

    heap_rec(L,N,0,,_,_,R).



%?- heap([a,b],R).

%R = [perm(1, [b, a]), perm(0, [a, b])] ;



%?- heap([a,b,c],R).

%R = [perm(5, [a, c, b]), perm(4, [c, a, b]), perm(3, [c, b, a]), perm(2, [b, c, a]), perm(1, [b, a, c]), perm(0, [a, b, c])] .





even_perm(L,R):-

    heap(L,R1),

    member(perm(A,R),R1),

    even(A).



%?- findall(R,even_perm([a,b,c],R),L).

%L = [[c, a, b], [b, c, a], [a, b, c]].





odd_perm(L,R):-

    heap(L,R1),

    member(perm(A,R),R1),

    odd(A).



%?- findall(R,odd_perm([a,b,c],R),L).

%L = [[a, c, b], [c, b, a], [b, a, c]].

So, is it the right way to do it? How can I improve it? Thanks.