Все разделы списка в прологе

Question

Я кодирую в Прологе. Я хочу найти все отдельные разделы списка. Я смотрю на список как набор здесь. Каждый раздел представляет собой набор множеств, в которых ни один не является пустым, объединение всех из них является основным множеством, а их попарное пересечение является пустым.

Answer 1

Сначала мы определяем вспомогательный предикат list_taken_rest/3:

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

Давайте посмотрим на запрос list_taken_rest/3 с первым аргументом, являющимся списком [a,b,c], В качестве ответов мы получаем альтернативные способы разделения элемента [a,b,c] между Xs а также Ys:

?- list_taken_rest([a,b,c], Xs, Ys).
   Xs = [a,b,c], Ys = []
;  Xs = [a,b],   Ys = [c]
;  Xs = [a,c],   Ys = [b]
;  Xs = [a],     Ys = [b,c]
;  Xs = [b,c],   Ys = [a]
;  Xs = [b],     Ys = [a,c]
;  Xs = [c],     Ys = [a,b]
;  Xs = [],      Ys = [a,b,c].

Далее мы определяем предикат list_partitioned/2, опираясь на list_taken_rest/3,

Как мы "гуляем" по списку [X|Xs]:

• Один раздел [X|Ys] строится.
• Этот раздел содержит X в качестве первого элемента и некоторых других предметов Xs в Ys,
• Все предметы в Xs которые не были приняты в Ys в конечном итоге в Zs,
• Действуем аналогично до Xs = [] держит.

list_partitioned ([], []).
list_partitioned ([X | Xs], [[X | Ys] | Pss]): -
   list_taken_rest (Xs, Ys, Zs),
   list_partitioned (Zs, Pss).

Готово! Давайте использовать list_partitioned/2 в некоторых запросах!

?- list_partitioned([1,2,3,4], Pss).          % query #1
   Pss = [[1,2,3,4]]
;  Pss = [[1,2,3],[4]]
;  Pss = [[1,2,4],[3]]
;  Pss = [[1,2],[3,4]] 
;  Pss = [[1,2],[3],[4]]
;  Pss = [[1,3,4],[2]]
;  Pss = [[1,3],[2,4]]
;  Pss = [[1,3],[2],[4]]
;  Pss = [[1,4],[2,3]]
;  Pss = [[1,4],[2],[3]]
;  Pss = [[1],[2,3,4]]
;  Pss = [[1],[2,3],[4]]
;  Pss = [[1],[2,4],[3]]
;  Pss = [[1],[2],[3,4]]
;  Pss = [[1],[2],[3],[4]].

?- list_partitioned([1,1,1], Pss).            % query #2
   Pss = [[1,1,1]]
;  Pss = [[1,1],[1]] 
;  Pss = [[1,1],[1]]                          %   (redundant answer)
;  Pss = [[1],[1,1]]
;  Pss = [[1],[1],[1]].

Обратите внимание, что list_partitioned/2 не заботится о наборах вообще:

• Если Ls является набором (как в запросе № 1), все ответы будут решениями.
• Если Ls содержит дубликаты (как в запросе № 2), мы получаем несколько лишних ответов.

Answer 2

part([Single], [[Single]]).

part([First|Others], [[First] | Result]) :-
    part(Others, Result).

part([First|Others], Result) :-
    part(Others, Temp),
    addElement(First, Temp, Result).

/* addElement(E, L, R), если R - тот же список списков, что и L, за исключением того, что у одного из его подсписков есть дополнительный E впереди */

addElement(Element, [FirstList | OtherLists], 
           [ [Element|FirstList] | OtherLists]).
addElement(Element, [FirstList | OtherLists], 
           [ FirstList | Temp] )
              :- addElement(Element, OtherLists, Temp).

Исполнение:

?- part([a,b,c,d],X).
X = [[a], [b], [c], [d]] ;
X = [[a], [b], [c, d]] ;
X = [[a], [b, c], [d]] ;
X = [[a], [c], [b, d]] ;
X = [[a], [b, c, d]] ;
X = [[a, b], [c], [d]] ;
X = [[b], [a, c], [d]] ;
X = [[b], [c], [a, d]] ;
X = [[a, b], [c, d]] ;
X = [[b], [a, c, d]] ;
X = [[a, b, c], [d]] ;
X = [[b, c], [a, d]] ;
X = [[a, c], [b, d]] ;
X = [[c], [a, b, d]] ;
X = [[a, b, c, d]] ;
false.