Prolog, removing supersets in a list of lists

Question

Let's say I have the following list:

List = [[a],[a,b],[a,c],[b,c],[b,d],[a,b,c],[a,b,d],[b,c,e],[b,d,e,f]]

The goal is to remove every list in the list that is a superset of a list in the list.

The list that contains the lists always has the following properties:

• The lists in the list are sorted by length
• Each list in the list is sorted

My initial idea was to simply start with the first list in the list and go through all other lists and remove the lists that are a superset. Next I'd look at the second list, et cetera.

After removing all supersets of the list [a] it should look like this:

List = [[a],[b,c],[b,d],[b,c,e],[b,d,e,f]]

Next the supersets of [b,c] should be removed:

List = [[a],[b,c],[b,d],[b,d,e,f]]

Last is the supersets of [b,d]:

List = [[a],[b,c],[b,d]]

And the line above should be the result.

I already made a predicate akin to the member predicate, but instead of taking a single element and comparing it to the list, this takes an entire list and compares it to the list:

memberList([],_).
memberList([X|Xs],Y) :-
    member(X,Y),
    memberList(Xs,Y).

This only works with lists.

?- memberList(a,[a,b,c]).
false.

?- memberList([a],[a,b,c]).
true .

?- memberList([a,b],[a,b,c]).
true .

But after this I'm a bit lost.

I tried the following which should remove the supersets of a single set, but it did not work:

removeSupersetsList(_,[],[]).
removeSupersetsList(X,[Y|Ys],[Y|Out]) :-
    not(memberList(X,Y)),
    removeSupersetsList(X,Ys,Out).
removeSupersetsList(X,[Y|Ys],Out) :-
    memberList(X,Y),
    removeSupersetsList(X,Ys,Out).

So I was wondering if someone could point me in the right direction to remove all supersets from a list or maybe even give the right predicate.

Answer 1

I'm using SWI-Prolog, where I find a crafted libray for ordered sets, and the required test, then using select/3 it's really easy to sanitize the list

rem_super_sets([], []).
rem_super_sets([L|Ls], R) :-
    (   select(T, Ls, L1), % get any T in Ls
        ord_subset(L, T)   % is T a superset of L ?
    ->  rem_super_sets([L|L1], R) % discard T, keep L for further tests
    ;   R = [L|L2],
        rem_super_sets(Ls, L2)
    ).

here a verification and the result

test :-
    List = [[a],[a,b],[a,c],[b,c],[b,d],[a,b,c],[a,b,d],[b,c,e],[b,d,e,f]],
    rem_super_sets(List, R),
    write(R).

?- test.
[[a],[b,c],[b,d]]
true.

Answer 2

-Hello Xylon, I think I understood your idea so I tried and created a solution using that idea. Here it is ( let me know if it suits your needs, or if it has bugs... )

memberList([],_).
memberList([X|Xs],Y) :-  member(X,Y),
                         memberList(Xs,Y).

%remove(ToRemove,ListWithSublists,LocRez,FinalRez)

%A list from ListWithSublists is removed,depending on ToRemove

% LocRez is accumulator used to obtain the FinalRez ( at the end )

remove(_,[],LocRez,LocRez) :- !.

remove(ToRemove,ListWithSublists,LocRez,FinalRez) :-     ListWithSublists=[Sublist|Rest],
                                                         memberList(ToRemove,Sublist),
                                                         remove(ToRemove,Rest,LocRez,FinalRez),!.

remove(ToRemove,ListWithSublists,LocRez,FinalRez) :-     ListWithSublists=[Sublist|Rest],
                                                         not(memberList(ToRemove,Sublist)),
                                                         append(LocRez,[Sublist],LocRezNew),
                                                         remove(ToRemove,Rest,LocRezNew,FinalRez),!.

removeSupersetsList(List,Rez) :- removeSupersetsList(List,[],Rez). % call this for testing

%removeSupersetsList(List,LocRez,Final)

%remove the Head from List from the List itself if needed(obtain Rez in the process)

%append the Head into our LocRez(get LocRezNew),

%call this recursively for the Rez

removeSupersetsList(List,LocRez,LocRez) :- List=[] ,!.
removeSupersetsList(List,LocRez,Final) :- ( List=[ToRemove|_] ; List=[ToRemove] ),
                                          remove(ToRemove,List,[],Rez),
                                          append(LocRez,[ToRemove],LocRezNew),
                                          removeSupersetsList(Rez,LocRezNew,Final),!.