序言中列表的所有分区 [英] All partitions of a list in prolog

问题描述

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

解决方案

首先，我们定义一个辅助谓词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.

当我们沿着"列表走"时[X|Xs]:

• 单个分区是 [X|Ys] 构建的.
• 该分区包含 X 作为第一个元素和 some 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).% 查询 #1Pss = [[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).% 查询 #2Pss = [[1,1,1]];Pss = [[1,1],[1]];Pss = [[1,1],[1]] %(冗余答案);Pss = [[1],[1,1]];Pss = [[1],[1],[1]].

请注意，list_partitioned/2 根本不关心集合:

• 如果 Ls 是一个集合(如查询 #1)，则所有答案都是解.
• 如果 Ls 包含重复项(如查询 #2)，我们会得到一些冗余答案.

I am coding in Prolog. I want to find all distinct partitions of a list. I look at a list as a set here. Each partition is a set of sets in which none is empty, the union of all of them is the main set, and the pairwise intersection of them is empty.

解决方案

First, we define an auxiliary predicate 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).

Let's look at a query of list_taken_rest/3 with the first argument being the list [a,b,c]. As answers we get alternative ways of parting the element of [a,b,c] between Xs and 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].

Next, we define the predicate list_partitioned/2, building on list_taken_rest/3.

As we "walk along" the list [X|Xs]:

• A single partition is [X|Ys] gets built.
• That partition contains X as the first element and some other items of Xs in Ys.
• All items in Xs that were not taken into Ys end up being in Zs.
• We proceed similarly until Xs = [] holds.

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]].

Note that list_partitioned/2 doesn't care about sets at all:

• If Ls is a set (like in query #1), all answers will be solutions.
• If Ls contains duplicates (like in query #2), we get some redundant answer(s).

这篇关于序言中列表的所有分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！