🚀 go-pugleaf

> From: dave@lsuc.UUCP
> Subject: miscellany re income tax planning system
> ...
> Third, I'm currently wrestling with the task of generating,
> for a list, every list which is a subset of that list. Thus,
> for [a,b,c,d], I want findall to be able to find each of
> [a,b] [a,c] [a,d] [a,b,c] [a,b,d] [a,c,d] [b,c] [b,d] [b,c,d] [c,d]. 

As a first attempt to solve your problem, you could use the following
"included(X,[a,b,c,d])" predicate:

    /* included(Set,SuperSet). True if all elements of Set in SuperSet, whatever
                               the order of the elements is.
    */
    included([X|Rest],SuperSet) :-
        member(X,SuperSet),
        del(X,SuperSet,SuperRest),
        included(Rest,SuperRest).
    included([],_).

However, this predicate generates all the permutations of the possible
solutions (i.e. [a,b,c] and [a,c,b] will be generated among other solutions).
To eliminate these permutations, you can use a slightly different version of
the "del" predicate:

    /* delUpTo(Element,OriginalList,ResultingList). Deletes first elements of
       OriginalList until it finds Element, then put result in ResultingList.
    */
    delUpTo(X,[X|Rest],Rest).
    delUpTo(X,[_|ButOne],Rest) :- delUpTo(X,ButOne,Rest).

    /* included(Set,SuperSet). True if all elements of Set in SuperSet,
                               in same order. Accepts [], [X] & full set.
    */
    included([X|Rest],SuperSet) :-
        member(X,SuperSet),
        delUpTo(X,SuperSet,SuperRest),
        included(Rest,SuperRest).
    included([],_).

There is still a small problem. "included" generates some undesired solutions
(i.e. empty list, single element lists and full set). You can filter them:

    /* subset(Set,SuperSet). Like "included", but rejects [], [X] & full set.
    */
    subset(Set,SuperSet) :-
        included(Set,SuperSet),
        filtered(Set,SuperSet).

    filtered(  []   ,   _   ) :- !,fail.
    filtered(  [_]  ,   _   ) :- !,fail.
    filtered(FullSet,FullSet) :- !,fail.
    filtered(   _   ,   _   ).

    included([X|Rest],SuperSet) :-
        member(X,SuperSet),
        delUpTo(X,SuperSet,SuperRest),
        included(Rest,SuperRest).
    included([],_).

    delUpTo(X,[X|Rest],Rest).
    delUpTo(X,[_|ButOne],Rest) :- delUpTo(X,ButOne,Rest).

As you mentioned, you can use the "findall" predicate to generate a list of
all solutions:

    findall(X,subset(X,[a,b,c,d]),ListOfSolutions)

Hope this helps.

B. Ibrahim	IBRAHIM@CGEUGE51.BITNET
		cernvax!cui!bertrand.uucp
		cui!bertrand@cernvax.UUCP
		bertrand@cui.unige.chunet