查找列表中覆盖 prolog 中整个列表的所有子序列

Question

我有一个序言作业，无法正确解决。

目标是找到给定列表的所有可能的子序列，这些子序列一起覆盖整个列表。 例如对于列表：

[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]
    [a] + [b] + [a] + [b] + [c] + [c, c]

...等等

有人可以帮我吗？

这是我到目前为止的代码：

    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).

它产生一些子序列，但不是全部。我对序言很陌生。

Answer 1

可能是：

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).

...导致 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.

但是，如果您想包括例如

[[c], [b, a]]

，那么可以用：

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).

...导致 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]].

请注意，这大量使用

[H|T]

表示法，以确保列表中至少有 1 个元素 - 这可以防止诸如无限地从列表中获取零个元素之类的缺陷。

上面的代码没有对重复元素进行特殊处理：

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

可以使用 distinct/1:

来防止这种答案重复

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