4

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.

false
  • 10,264
  • 13
  • 101
  • 209
voluminat0
  • 866
  • 2
  • 11
  • 21

2 Answers2

4

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.

false
  • 10,264
  • 13
  • 101
  • 209
  • since I am new to prolog, I am not quite sure what would be a solution.. I also don't really understand what the 'wrong' part in my thinking is. – voluminat0 Dec 12 '14 at 13:01
  • 4
    @ValentijnSpruyt to state another way: your query to `permutation(S, Res)` is too "open-ended". Both arguments are variable. On backtracking, it will continue to generate and try permutations, *ad infinitum*, with ever increasing numbers of elements. You need to constrain it. – lurker Dec 12 '14 at 17:41
  • 2
    @lurker: What about posting a version that terminates "as good as a possible" Let's see how far we can go! – false Dec 12 '14 at 18:18
  • 2
    @ValentijnSpruyt: Did you read other answers from the tag [tag:failure-slice]? – false Dec 12 '14 at 18:24
3

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
| ?-
lurker
  • 56,987
  • 9
  • 69
  • 103