Prolog loop after results

Question

So I wrote this predicate to find all possible subsets + permutations of a list. I get the correct output but for some reason the program keeps looping after giving me all the (correct) results.

What am I doing wrong?

% Gets all subsets of a list
aSubset([], []).
aSubset([E|Tail], [E|NTail]):- aSubset(Tail, NTail).
aSubset([_|Tail], NTail):- aSubset(Tail, NTail).

% gets all subsets and permutates them
allSubsets([],[]).
allSubsets(X, Res) :- permutation(S, Res), aSubset(X, S).

the results that I get for allSubsets([1,2,3], X) are:

4 ?- allSubsets([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1,2] ;
X = [1,3] ;
X = [2,3] ;
X = [2,1] ;
X = [3,1] ;
X = [3,2] ;
X = [1,2,3] ;
X = [1,3,2] ;
X = [2,1,3] ;
X = [2,3,1] ;
X = [3,1,2] ;
X = [3,2,1] ;
Action (h for help) ? abort
% Execution Aborted

where I have to abort the loop in the last two lines.

Thanks in advance.

Answer 1

Not only allSubset([1,2,3], X) loops, but also the much shorter allSubset([], X).

The following program fragment (failure-slice) loops already. So no need to look any further.

allSubsets([],[]) :- false.
allSubsets(X, Res) :-
   permutation(S, Res), false,
   aSubset(X, S).

To improve this, you need to change something in the visible part. Currently, only Arg2 (Res) can influence the goal permutation(S, Res), Arg1 (X) occurs only in the second goal, when it is already too late to influence (universal) termination of the first.

Answer 2

One way to get there is a slight modification of your current code:

% Gets all subsets of a list
aSubset([], []).
aSubset([E|Tail], [E|NTail]):- aSubset(Tail, NTail).
aSubset([_|Tail], NTail):- aSubset(Tail, NTail).

% gets all subsets and permutates them
allSubsets([],[]).
allSubsets(X, Res) :- aSubset(X, S), permutation(S, Res).

So, rather than do an unbounded permutation first, generate a subset of the known list first (a finite number of solutions), then permute the known subset (also a finite number of solutions). Backtracking will do this across all permutations of all subsets:

| ?- allSubsets([1,2,3], L).

L = [1,2,3] ? a

L = [1,3,2]

L = [2,1,3]

L = [2,3,1]

L = [3,1,2]

L = [3,2,1]

L = [1,2]

L = [2,1]

L = [1,3]

L = [3,1]

L = [1]

L = [2,3]

L = [3,2]

L = [2]

L = [3]

L = []

(2 ms) no
| ?-