prolog - 使用 prolog 将一个集合划分为 n 个子集

Question

我正在努力解决以下问题，使用序言将一个集合划分为 n 个子集。

例如，我给程序输入:X = [1,2,3,4], N=3 然后我得到

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

或者我给出输入:X = [1,2,3,4], N=2 然后我得到

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

Answer 1

这个答案扩展了 @lurker's previous answer具有附加(冗余)约束。

使用 dcg我们定义了以下辅助非终结符:

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

我们通过预先添加一个 phrase/2 目标来利用这些 DCG:

list_partitionedNU(Es, Xss) :-
   phrase(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]]
;  false.

在我看来当然没问题。

接下来，让我们谈谈通用终止。像 list_partitioned(Es, [[a,b,c]]) 这样的目标不会普遍终止——即使它们是微不足道的。 list_partitionedNU/2 解决了这个问题:

?- list_partitioned(Es, [[a,b,c]]).
   Es = [a,b,c]
;  NONTERMINATION

?- list_partitionedNU(Es, [[a,b,c]]).
   Es = [a,b,c]
;  false.                                          % terminates universally

这些额外的约束可以显着加快某些查询的速度。

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

好的!当然，加速取决于所用列表的实际长度...... YMMV :)