使用 prolog 将集合划分为 n 个子集 [英] partition a set into n subsets using prolog
问题描述
我正在努力解决以下问题,使用 prolog 将一个集合划分为 n 个子集.
例如,我给程序作为输入:X = [1,2,3,4], N=3 我得到
Res = [[1,2], [3], [4]]水库 = [[1,3], [2], [4]]水库 = [[1,4], [2], [3]]水库 = [[2,3], [1], [4]]水库 = [[2,4], [1], [3]]水库 = [[3,4], [1], [2]]
或者我输入:X = [1,2,3,4], N=2 我得到
Res = [[1,2], [3,4]]水库 = [[1,3], [2,4]]水库 = [[1,4], [2,3]]水库 = [[1,2,3], [4]]水库 = [[1,2,4], [3]]水库 = [[1,3,4], [2]]水库 = [[2,3,4], [1]]
这个答案扩展@lurker's previous answer 附加(冗余)约束.
使用 dcg 我们定义以下辅助非-终端:
<上一页>相同长度([])-> [].% DCG 风格的 same_length/2相同长度([_|Es])-> [_],相同长度(Es).相同长度1([_|Es])-> [_],相同长度(Es).相同长度1([])-> [].same_lengths1([Es|Ess]) --> same_length1(Es),same_lengths1(Ess).我们通过预先添加 phrase/2
目标来利用这些 DCG:
对于一些普通的测试用例,我们还能得到合理的答案吗?
<上一页>?- list_partitionedNU([a,b,c], Xss).Xss = [[a],[b],[c]];Xss = [[a],[b,c]];Xss = [[a,b],[c]];Xss = [[a,c],[b]];Xss = [[a,b,c]];错误的.在我看来当然没问题.
接下来,我们来谈谈通用终止.像 list_partitioned(Es, [[a,b,c]])
这样的目标不会普遍终止——即使它们是微不足道的.list_partitionedNU/2
解决了这个问题:
这些额外的限制可以大大加快一些查询.
使用 SICStus Prolog 4.4.0:
<上一页>|?- use_module(库(之间),[编号列表/3]).是的|?- numlist(1, 14, _Es),长度(_Xss,10),成员(P_2,[list_partitioned,list_partitionedNU]),call_time((call(P_2,_Es,_Xss), false ; true), T_msec).P_2 = list_partitioned,T_msec = 29632?;P_2 = list_partitionedNU, T_msec = 600 ?;% 快 40 倍不好的!当然,加速取决于所用列表的实际长度...... YMMV :)
I'm struggling with the following problem, partition a set into n subsets using prolog.
So for example, I give as input to program: X = [1,2,3,4], N=3 and I get
Res = [[1,2], [3], [4]]
Res = [[1,3], [2], [4]]
Res = [[1,4], [2], [3]]
Res = [[2,3], [1], [4]]
Res = [[2,4], [1], [3]]
Res = [[3,4], [1], [2]]
or I give as input: X = [1,2,3,4], N=2 and I get
Res = [[1,2], [3,4]]
Res = [[1,3], [2,4]]
Res = [[1,4], [2,3]]
Res = [[1,2,3], [4]]
Res = [[1,2,4], [3]]
Res = [[1,3,4], [2]]
Res = [[2,3,4], [1]]
This answer extends @lurker's previous answer with additional (redundant) constraints.
Using dcg we define the following auxiliary non-terminals:
same_length([]) --> []. % DCG-style same_length/2 same_length([_|Es]) --> [_], same_length(Es). same_length1([_|Es]) --> [_], same_length(Es). same_lengths1([]) --> []. same_lengths1([Es|Ess]) --> same_length1(Es), same_lengths1(Ess).
We utilize these DCGs by adding a phrase/2
goal upfront:
list_partitionedNU(Es, Xss) :- phrase(same_lengths1(Xss), Es), list_partitioned(Es, Xss).
Do we still get reasonable answers for some vanilla test case?
?- list_partitionedNU([a,b,c], Xss). Xss = [[a],[b],[c]] ; Xss = [[a],[b,c]] ; Xss = [[a,b],[c]] ; Xss = [[a,c],[b]] ; Xss = [[a,b,c]] ; false.
Sure looks okay to me.
Next, let's talk about universal termination. Goals like list_partitioned(Es, [[a,b,c]])
do not terminate universally—even though they are trivial. list_partitionedNU/2
fixes this:
?- list_partitioned(Es, [[a,b,c]]). Es = [a,b,c] ; NONTERMINATION ?- list_partitionedNU(Es, [[a,b,c]]). Es = [a,b,c] ; false. % terminates universally
These additional constraints can speedup some queries considerably.
Using SICStus Prolog 4.4.0:
| ?- use_module(library(between), [numlist/3]). yes | ?- numlist(1, 14, _Es), length(_Xss, 10), member(P_2, [list_partitioned,list_partitionedNU]), call_time((call(P_2,_Es,_Xss), false ; true), T_msec). P_2 = list_partitioned , T_msec = 29632 ? ; P_2 = list_partitionedNU, T_msec = 600 ? ; % 40x faster no
Alright! Of course, the speedup depends on the actual lengths of the lists used... YMMV:)
这篇关于使用 prolog 将集合划分为 n 个子集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!