Search code examples
prolog

How to create a list without using findall? Prolog

I am generating permutations:

takeout(X,[X|T],T).
takeout(X,[F|R],[F|S]):-
    takeout(X,R,S).

perm([],[]).
perm([X|Y],Z):-
    perm(Y,W),
    takeout(X,Z,W).

I want to know how to create a list of all the permutations without using findall.

Example:

?-perm([1,2,3],List).
List = [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]
Solution

  • The idea is to generate permutations and test if you already created this permutation. I'm using the inbuild predicate permutation/2.

    perm(Ori,Out):-
    perm(Ori,[],Out).

perm(Ori,Acc,Ret):-
    permutation(Ori,Perm),
    \+ member(Perm,Acc),
    !,
    perm(Ori,[Perm|Acc],Ret).
perm(_,L,L).

?- perm([1,2,3],E).
E = [[3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]].

    The code is not the fastest one since it checks multiple times for membership.