使用 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 之前的答案 带有附加(冗余)约束.

使用 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 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屋！