序言中列表的所有分区

Question

我正在用 Prolog 编码。我想找到列表的所有不同分区。我在这里将列表视为一组。每一个partition都是一组none为空的集合，所有的并集为主集，两两交集为空

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]。作为答案，我们得到了在 Xs 和 Ys 之间分离 [a,b,c] 元素的替代方法：

?- 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_taken_rest/3.

的基础上定义谓词 list_partitioned/2

正如我们 "walk along" 列表 [X|Xs]:

单个分区 [X|Ys] 已构建。
该分区包含作为第一个元素的 X 和 Ys 中 Xs 的一些其他项目。
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).

/* 添加元素（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.

序言中列表的所有分区

All partitions of a list in prolog

prolog