序言中列表的所有分区

Question

我在 Prolog 中编码。我想找到列表的所有不同分区。我在这里将列表视为一组。每个分区都是一个集合，其中没有一个是空的，它们的并集是主集，它们的成对交是空的。

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第一个参数是 list的查询[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]构建单个分区。
• 该分区包含inX的第一个元素和一些其他项目。XsYs
• 中的所有项目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），我们会得到一些冗余答案。