all subsets with all elements of a list in prolog

Question

I'm trying to compute a list of all subsets of a given list with all its elements, but so far I've only succeeded to find subsets of two elements, but this is not a right solution for my problem.. can anyone help me? I know that problems like this are solved by using backtracking method, but in Prolog, I'm not sure how this should be written.. The source code is like this:

  subs(_, [], []).
  subs(H, [H1|Tail], [[H,H1]|Ta]):-
       subs(H, Tail, Ta).

  generatesubs([], []).
  generatesubs([H], [H]).
  generatesubs([H|Tail], [R|Ta]):-
      subs(H, Tail, R),
      generatesubs(Tail, Ta).

  main1([], []).
  main1([H], [H]):-
     is_list(H).
  main1([H|Tail], [H|Ta]):-
     is_list(H),
  main1(Tail, Ta).
  main1([_|Tail], Ta):-
     main1(Tail, Ta).

  main([], []).
  main(H ,R):-
      generatesubs(H, G),
      main1(G,R).

Thanks in advance! :)

for instance, if we call main([2,3,4,5], R), R should be: [[2,3], [2,4], [2,5], [2,3,4], [2,3,5], [3,4,5]] — Nelly, Nov 24 '15 at 22:28
Ok, why not go for the entire https://en.m.wikipedia.org/wiki/Power_set ? (That would include `[2,3,4,5]` and `[]` as well as all the singleton subsets.) — repeat, Nov 25 '15 at 06:19
The powerset would be a principled approach, but if you wanted to be vulgar, you could just take [the powerset code from this answer](http://stackoverflow.com/a/10341354/812818) and limit it to the N>2, N — Daniel Lyons, Nov 25 '15 at 07:24
@DanielLyons. Wouldn't this also require using `setof/3` (or, at least, `findall/3`)? — repeat, Nov 27 '15 at 06:11

score 3 · Answer 1 · edited May 23 '17 at 12:33

Use dcg!

list_allsubseqs(Es, Uss) :-
   list_acc_allsubseqs(Es, [[]], Uss).

lists_prependum([]      , _) --> [].
lists_prependum([Es|Ess], E) --> [[E|Es]], lists_prependum(Ess, E).

list_acc_allsubseqs([]    , Uss , Uss).
list_acc_allsubseqs([E|Es], Uss0, Uss) :-
   list_acc_allsubseqs(Es, Uss0, Uss1),
   phrase(lists_prependum(Uss1,E), Uss, Uss1).

Sample queries:

?- list_allsubseqs([], Xss).
Xss = [[]].

?- list_allsubseqs([a], Xss).
Xss = [[a], []].

?- list_allsubseqs([a,b], Xss).
Xss = [[a,b], [a], [b], []].

?- list_allsubseqs([a,b,c], Xss).
Xss = [[a,b,c], [a,b], [a,c], [a], 
         [b,c],   [b],   [c], []].

?- list_allsubseqs([a,b,c,d], Xss).
Xss = [[a,b,c,d], [a,b,c], [a,b,d], [a,b], [a,c,d], [a,c], [a,d], [a],
         [b,c,d],   [b,c],   [b,d],   [b],   [c,d],   [c],   [d], []].

So... how does list_allsubseqs/2 fare in comparison to findall/3 plus list_subseq/2? What about memory consumption? What about runtime? Let's dig deeper!

First, for the sake of completeness, here's the code of good-ol' vanilla list_subseq/2:

list_subseq([], []).
list_subseq([E|Es], [E|Xs]) :- list_subseq(Es, Xs).
list_subseq([_|Es],    Xs ) :- list_subseq(Es, Xs).

In the following we use swi-prolog version 7.3.11 (64-bit).

:- set_prolog_flag(toplevel_print_anon, false).  % hide some substitutions
:- set_prolog_stack(global, limit(2*10**9)).     % cf. SWI-FAQ on "stack sizes"

Let's investigate!

?- between(18, 22, N),
   numlist(1, N, _Es),
   member(How, [findall_subseq, list_allsubseqs]),
   garbage_collect,
   call_time(( How =  findall_subseq, findall(Xs,list_subseq(_Es,Xs),_) 
             ; How = list_allsubseqs, list_allsubseqs(_Es,_)), T_in_ms),
   statistics(globalused, Mem_in_B).

  N = 18, How =  findall_subseq, Mem_in_B =    62_915_848, T_in_ms =   185
; N = 18, How = list_allsubseqs, Mem_in_B =    12_584_904, T_in_ms =    22
;
  N = 19, How =  findall_subseq, Mem_in_B =   132_121_888, T_in_ms =   361
; N = 19, How = list_allsubseqs, Mem_in_B =    25_167_888, T_in_ms =    42
;
  N = 20, How =  findall_subseq, Mem_in_B =   276_825_400, T_in_ms =   804
; N = 20, How = list_allsubseqs, Mem_in_B =    50_333_784, T_in_ms =    80
;
  N = 21, How =  findall_subseq, Mem_in_B =   578_815_312, T_in_ms = 1_973
; N = 21, How = list_allsubseqs, Mem_in_B =   100_665_504, T_in_ms =   154
;
  N = 22, How =  findall_subseq, Mem_in_B = 1_207_960_936, T_in_ms = 3_966
; N = 22, How = list_allsubseqs, Mem_in_B =   201_328_872, T_in_ms =   290.

all subsets with all elements of a list in prolog

1 Answers1