gnu Prolog powerset modification

Question

So i got this for powerset:

powerset([], []).
powerset([H|T], P) :- powerset(T,P).
powerset([H|T], [H|P]) :- powerset(T,P).

This generates all sets of a list. Is it possible to generate all sets in list order.

Example:

List = [a,b,c]

I want to get

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

Note there is no [a,c] in this list of subsets since these are subsets starting from the left and going to the right.

I've tried using a combination of append and recursion, but that didn't work out as i wanted it to. Little stumped at this point.

Thanks.

Answer 1

How about

powerset(L, [H|T]):-
  append([H|T], _, L).
powerset([_|L], P):-
  powerset(L, P).

Answer 2

You want all subsequences substrings (definition). Grammars (DCGs) are best for this:

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

... --> [] | [_], ... .

?- Es = [_|_], phrase((..., seq(Es), ...), [A,B,C]).
Es = [A] ;
Es = [A, B] ;
Es = [A, B, C] ;
Es = [B] ;
Es = [B, C] ;
Es = [C] ;
false.

(SWI-Prolog)

Answer 3

I know this an old post, but I'm not gonna update it for no reasons. the answer which is accepted with all the respect, generates all subsets separably, and does not generate a powerset.

a few days ago I was trying to implement a powerSet/2 predicate, without use of built-in predicate bagof/2. but even with bagof/2 and setof/2 it's not very easy problem for beginners (generating all subset separably is another problem and much easier). so after implementing the solution I thought it's better to put it here in order to prevent people who are searching for this topic from mistakes.

My solution (without bagof/2)

generate(X, [Y], [[X| Y]]).

generate(X, S, P) :-
        S = [H| T],
        append([X], H, Temp),
        generate(X, T, Rest),
        append([Temp], Rest, P), !.

powerSet([], [[]]).

powerSet(Set, P) :-
        Set = [H| T],
        powerSet(T, PsT),
        generate(H, PsT, Ps),
%       write('trying to push '), print(H), write(' to '),
%       write('all elements of powerset of '), print(T), write(' which is '),
%       print(PsT), nl,
%       write('and the result is '), print(Ps), nl, nl,
        append(Ps, PsT, P), !.

code will be understood if consulted with the commented lines.

another solution is available here which uses built-in predicate bagof/3.

probably it would be more helpful now.

Answer 4

How about this:

powerset(A,B):-
    append(A,_,B);
    append(_,A,B).

test():-
    setof(X,powerset(X,[1,2,3]),L),
    writeln(L).