prolog中列表的所有分区 [英] 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
作为第一个元素和 一些Ys
中的其他Xs
项. Xs
中未纳入Ys
的所有项目最终都在Zs
中.- 我们继续进行类似的操作,直到
Xs = []
成立.
完成!让我们在一些查询中使用 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 ofXs
inYs
. - All items in
Xs
that were not taken intoYs
end up being inZs
. - 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).
这篇关于prolog中列表的所有分区的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!