Найти все списки подсписков, которые при объединении дают заданный список

Question

Я написал эту функцию, которая в качестве первого параметра дает список списков, во втором параметре она генерирует результат объединения всех списков.

appall([],[]).
appall([H|T],V) :- appall(T,V1), append(H,V1,V).

Однако я хочу, чтобы она работала с другим наоборот - appall(X,[1,2,3]) - чтобы дать мне X = [[],[1,2,3]], затем X=[[1],[2,3]] и так далее. Это не работает, потому что вызов appall(T, V1) не уменьшается.

Как мне это исправить?

Answer 1

Вот одно решение:

split([],[]).
split([Head|Tail],[[Head]|Split]) :-
    split(Tail,Split).
split([Head|Tail],[[Head|List]|Split]) :-
    split(Tail,[List|Split]).

Например:

?- split([1,2,3,4],Lists), split(Recover,Lists).
Lists = [[1], [2], [3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1], [2], [3, 4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1], [2, 3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1], [2, 3, 4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2], [3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2], [3, 4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2, 3], [4]],
Recover = [1, 2, 3, 4] ;
Lists = [[1, 2, 3, 4]],
Recover = [1, 2, 3, 4] ;
false.

Это решение основано на следующем наблюдении. Я буду ссылаться на сплющенный список как список ввода , а нераспечатанный список - как список вывода . В рекурсивном случае входной список имеет форму [H|T], а split(T,R) выполняется по предположению. Необходимо рассмотреть три случая.

1. Если R = [], мы можем начать создавать новый список, последний элемент которого H.
2. Если R = [_|_], мы можем начать создавать новый список, последний элемент которого H.
3. Если R = [L|_], мы можем продолжить построение L, добавив от H к L.

В каждом случае мы получаем действительные списки вывода. Первые два случая реализуются вторым предложением split/2 (неважно, R = [] или R = [_|_]), а третье - третьим.