我正在努力解决以下问题,使用 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 之前的答案 带有附加(冗余)约束.
使用 dcg 我们定义了以下辅助非-终端:
same_length([]) --> [].% DCG 风格的 same_length/2same_length([_|Es]) --> [_], same_length(Es).same_length1([_|Es]) --> [_], same_length(Es).same_lengths1([]) --> [].same_lengths1([Es|Ess]) --> same_length1(Es),same_lengths1(Ess).我们通过预先添加一个 phrase/2 目标来利用这些 DCG:
list_partitionedNU(Es, Xss) :-短语(same_lengths1(Xss),Es),list_partitioned(Es, Xss).对于一些普通的测试用例,我们还能得到合理的答案吗?
?- 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 修复了这个:
?- list_partitioned(Es, [[a,b,c]]).Es = [a,b,c];终止?- list_partitionedNU(Es, [[a,b,c]]).Es = [a,b,c];错误的.% 普遍终止这些额外的约束可以大大加快某些查询的速度.
使用 SICStus Prolog 4.4.0:
|?- use_module(图书馆(之间), [numlist/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 universallyThese 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 noAlright! Of course, the speedup depends on the actual lengths of the lists used... YMMV:)
更多推荐
使用 prolog 将一个集合划分为 n 个子集
发布评论