Find all subsequences of a list that cover the whole list in prolog

Question

I have a prolog assignmment that I am not able to solve correctly.

The goal is to find all possible subsequences of a given list that together cover the whole list. For example for a list: [a,b,a,b,c,c,c]

The results would be:

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

... etc.

Could anyone help me with this?

This is my code so far:

    allSubsequences([X|Xs], [[X]|Y]):-
        allSubsequences(Xs, Y).
    allSubsequences([X|Xs], [Y|[Z]]):-
        all_splits([X|Xs], Y, Z),
        Z \= [].

    all_splits([], [], []).
    all_splits([X|Xs], [X], Xs).
    all_splits([X|Xs], [X|Ys], Zs) :- 
        all_splits(Xs, Ys, Zs).

It produces some subsequences but not all of them. Im very new to prolog.

Answer 1

At the end it is just traveling the list and deciding whether to cut or not...

split([], []).
split([H|T], [[H|O1]|O2]) :- split(T, O1, O2).

split([H|T], [H|O1], O2) :- split(T, O1, O2).
split(H, [], O) :- split(H, O).

Answer 2

Could be:

sublists_not_empty([H|T], [SL|SLs]) :-
    sublists_not_empty_([H|T], [SL|SLs]).

sublists_not_empty_([], []).
sublists_not_empty_([H|T], [SL|SLs]) :-
    sublist_not_empty([H|T], SL, R),
    sublists_not_empty_(R, SLs).

sublist_not_empty([H|T], [E|SL], R) :-
    sublist_not_empty_([H|T], [E|SL], R).

% Finished when reached end of list
sublist_not_empty_([], [], []).
% Pick this element
sublist_not_empty_([H|T], [H|SL], R) :-
    sublist_not_empty_(T, SL, R).
% Do not pick this element
sublist_not_empty_([H|T], SL, [H|R]) :-
    sublist_not_empty_(T, SL, R).

... result in swi-prolog:

?- sublists_not_empty([a,b,c], SLs).
SLs = [[a, b, c]] ;
SLs = [[a, b], [c]] ;
SLs = [[a, c], [b]] ;
SLs = [[a], [b, c]] ;
SLs = [[a], [b], [c]] ;
SLs = [[a], [c], [b]] ;
SLs = [[b, c], [a]] ;
SLs = [[b], [a, c]] ;
SLs = [[b], [a], [c]] ;
SLs = [[b], [c], [a]] ;
SLs = [[c], [a, b]] ;
SLs = [[c], [a], [b]] ;
SLs = [[c], [b], [a]] ;
false.

However, if you want to include e.g. [[c], [b, a]], then can use instead:

sublists_not_empty_perm([H|T], [SL|SLs]) :-
    sublists_not_empty_perm_([H|T], [SL|SLs]).

sublists_not_empty_perm_([], []).
sublists_not_empty_perm_([H|T], [[PH|PT]|SLs]) :-
    % R is remainder
    sublist_perm([H|T], [PH|PT], R),
    sublists_not_empty_perm_(R, SLs).

% Finished when reached end of list
sublist_perm([], [], []).
% Can finish anytime
sublist_perm([H|T], [], [H|T]).
% Select an element
sublist_perm([H|T], [E|SL], R) :-
    select(E, [H|T], SR),
    sublist_perm(SR, SL, R).

... result in swi-prolog:

?- sublists_not_empty_perm([a,b,c], SLs).
SLs = [[a], [b], [c]] ;
SLs = [[a], [b, c]] ;
SLs = [[a], [c], [b]] ;
SLs = [[a], [c, b]] ;
SLs = [[a, b], [c]] ;
SLs = [[a, b, c]] ;
SLs = [[a, c], [b]] ;
SLs = [[a, c, b]] ;
SLs = [[b], [a], [c]] ;
SLs = [[b], [a, c]] ;
SLs = [[b], [c], [a]] ;
SLs = [[b], [c, a]] ;
SLs = [[b, a], [c]] ;
SLs = [[b, a, c]] ;
SLs = [[b, c], [a]] ;
SLs = [[b, c, a]] ;
SLs = [[c], [a], [b]] ;
SLs = [[c], [a, b]] ;
SLs = [[c], [b], [a]] ;
SLs = [[c], [b, a]] ;
SLs = [[c, a], [b]] ;
SLs = [[c, a, b]] ;
SLs = [[c, b], [a]] ;
SLs = [[c, b, a]].

Notice that this is heavily using [H|T] notation, to ensure at least 1 element in a list - which prevents flaws such as infinitely taking zero elements from a list.

The above code does not treat duplicate elements specially:

?- sublists_not_empty_perm([a,a], SLs).
SLs = [[a], [a]] ;
SLs = [[a, a]] ;
SLs = [[a], [a]] ;
SLs = [[a, a]].

Such answer duplication can be prevented using distinct/1:

?- distinct(sublists_not_empty_perm([a,a], SLs)).
SLs = [[a], [a]] ;
SLs = [[a, a]] ;
false.