How to create a list without using findall? Prolog

user_1420056 0
Viewed 142

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]]
prolog
2 Answers

Group permutations by the element it starts with.

  1. Take an element X and create permutations Ys1 without it in the original list.
  2. Adding this element X as the first element of all these permutations we have the list XP of permutations starting with X. Appending all the groups will give you all permutations.
cons(X, Xs, [X|Xs]).
perm([], [[]]).
perm(Xs, Ys) :-
    dif(Xs, []),
    maplist({Xs}/[X, XP]>>(select(X, Xs, Xs1),
                           perm(Xs1, Ys1),
                           maplist(cons(X), Ys1, XP)),
            Xs, Yss),
    append(Yss, Ys).

?- perm([1, 2, 3], X).
X = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ;
false.
?- length(Y, 8), perm(Y, X), length(X, N). %8 factorial
N = 40320
user_44371900

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.

user_80806480
Related