4

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.

false
  • 10,264
  • 13
  • 101
  • 209
Matt
  • 7,049
  • 7
  • 50
  • 77

4 Answers4

6

How about

powerset(L, [H|T]):-
  append([H|T], _, L).
powerset([_|L], P):-
  powerset(L, P).
gusbro
  • 22,357
  • 35
  • 46
  • Thanks! That makes sense. I was close. Seems to always be the case. – Matt Nov 10 '10 at 23:19
  • This does **not** produce the full powerset. For instance, it fails to produce [a, c] when asked what the powerset of [a, b, c] is. – RasmusJ Sep 15 '16 at 07:07
  • @RasmusJ: Have you seen the question ? It clearly states that [a,c] should not be an answer for input [a,b,c]. OP wants "sets in list order" (check OP sample input/output for clarification) – gusbro Sep 15 '16 at 17:00
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.

VahidM
  • 287
  • 1
  • 2
  • 14
3

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.
false
  • 10,264
  • 13
  • 101
  • 209
0

How about this:

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

test():-
    setof(X,powerset(X,[1,2,3]),L),
    writeln(L).
Sahil Jain
  • 629
  • 7
  • 12