All combinations of a list without doubles in Prolog

Question

Is there a simple way of getting all the combinations of a list without doubles. Without doubles I mean also no permutations of each other. So no [a,b,c] and [c,a,b] or [c,b,a].

So for the input [a,b,c] the output would be:

[a]
[b]
[c]
[a,b]
[a,c]
[b,c]
[a,b,c]

I can only find solutions WITH the doubles (permutations)

Answer 1

The solution to this problem is rather simple: there is evidently only one combination out of the empty set: the empty set:

combs([],[]).

Furthermore for each element, you can decide whether you add it or not:

combs([H|T],[H|T2]) :-
    combs(T,T2).
combs([_|T],T2) :-
    combs(T,T2).

Since you pick (or drop) in the order of the list, this guarantees you that you later will not redecide to pick a. If you feed it [a,b,c], it will never generate something like [b,a,c], because once it has decided to pick/drop a, it cannot add b and re-decide on a.

Running this gives:

?- combs([a,b,c],L).
L = [a, b, c] ;
L = [a, b] ;
L = [a, c] ;
L = [a] ;
L = [b, c] ;
L = [b] ;
L = [c] ;
L = [].

In case you want to generate it the opposite way (have more of a test to first drop elements, instead of adding them, you can simply swap the recursive statements):

combs([],[]).

combs([_|T],T2) :-
    combs(T,T2).
combs([H|T],[H|T2]) :-
    combs(T,T2).

In that case the result will be:

?- combs([a,b,c],L).
L = [] ;
L = [c] ;
L = [b] ;
L = [b, c] ;
L = [a] ;
L = [a, c] ;
L = [a, b] ;
L = [a, b, c].

EDIT

Given you want to exclude the empty list, either you can do it simply by adding another check in your call:

?- combs([a,b,c],L),L \= [].

You can define this in a function like:

combs_without_empty1(LA,LB) :-
    combs_without_empty1(LA,LB),
    LB \= [].

Or by rewriting the comb/2 function. In that case you better use an accumulator that counts the current amount of selected elements:

combs_without_empty(L,C) :-
    combs_without_empty(L,0,C).

The combs_without_empty/3 is a bit more complicated. In case the list contains only one element, one should check if N is greater than zero. If that is the case, we can choose whether to add the element or not. If N is zero, we have to include it. So:

combs_without_empty([A],_,[A]).
combs_without_empty([_],N,[]) :-
    N > 0.

We also have to implement a recursive part that will increment N given we select an element:

combs_without_empty([_|T],N,T2) :-
    combs_without_empty(T,N,T2).
combs_without_empty([H|T],N,[H|T2]) :-
    N1 is N+1,
    combs_without_empty(T,N1,T2).

Putting it all together gives:

combs_without_empty(L,C) :-
    combs_without_empty(L,0,C).

combs_without_empty([A],_,[A]).
combs_without_empty([_],N,[]) :-
    N > 0.

combs_without_empty([_|T],N,T2) :-
    combs_without_empty(T,N,T2).
combs_without_empty([H|T],N,[H|T2]) :-
    N1 is N+1,
    combs_without_empty(T,N1,T2).

Which produces:

?- combs_without_empty([a,b,c],L).
L = [c] ;
L = [b, c] ;
L = [b] ;
L = [a, c] ;
L = [a] ;
L = [a, b, c] ;
L = [a, b] ;
false.

Answer 2

A clean solution without ancillary checks for empty list would be simply to exclude empty lists from the rules. The base case should be a single element combination:

comb_without_empty([H|_], [H]).   % Simple case of one element comb
comb_without_empty([_|T], C) :-   % Combinations of the tail w/o head
    comb_without_empty(T, C).
comb_without_empty([H|T], [H|C]) :-  % Combinations of the tail including head
    comb_without_empty(T, C).

| ?- comb_without_empty([a,b,c], L).

L = [a] ? a

L = [b]

L = [c]

L = [b,c]

L = [a,b]

L = [a,c]

L = [a,b,c]

(1 ms) no
| ?-