prolog - 序言中列表的所有分区

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第一个参数是列表 [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).

Done! Let's use list_partitioned/2 in some queries!

?- 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)，我们得到一些冗余答案。