使用具体化的约束条件使3个数字连续

Question

以下是我SWI-Prolog程序的概要：

:- use_module(library(clpfd)).

consec1(L) :-
   L=[L1,L2,L3,L4,L5,L6,L7,L8,L9],
   L ins 1..9,
   ...,
   abs(L5-L4)#=1,
   all_different(L),
   labeling([],L)

abs(L5-L4)#=1 表示 L5 和 L4 相邻。如果我想让三个数字相邻，例如 L3、L4 和 L5，如何使用具体化约束来实现？

例如，L3=4，L5=5，L4=6 或 L4=7，L5=8，L3=9。

- mmgro27

---

你的意思是 'consecutive' 指例如 (L2#=L1+1 #/\ L3#=L2+1) #\/ (L2#=L1-1 #/\ L3#=L2-1) 吗？ - repeat

此外，这种关系是否适用于L的所有3个相邻成员，还是只适用于某些/任何成员？ - repeat

Answer 1

这个实现是按照你在评论中提到的连续性。对于一个包含N个值的列表，我们需要足够的空间让所有值都适合其中，并且所有值都必须不同。

consecutive([]).  % debatable case
consecutive(Xs) :-
   Xs = [_|_],
   length(Xs, N),
   all_different(Xs),
   max_of(Max, Xs),
   min_of(Min, Xs),
   Max-Min #= N-1.

max_of(Max, [Max]).
max_of(Max0, [E|Es]) :-
   Max0 #= max(E,Max1),
   max_of(Max1, Es).

min_of(Min, [Min]).
min_of(Min0, [E|Es]) :-
   Min0 #= min(E, Min1),
   min_of(Min1, Es).

- false

Answer 2

TL;DR: 如果内容过长无法在评论中展示，可以使用SICStus Prolog的专门的clpfd约束条件 maximum/2 和 minimum/2 作为 min_of/2 和 max_of/2 的替代品。

---

这个答案是在 这个之前的答案 上进行的补充。最近版本的SICStus Prolog提供了专门的clpfd约束条件 maximum/2 和 minimum/2 作为 min_of/2 和 max_of/2 的替代品。

使用以下用于基准测试的代码^1,2 ...

:- use_module(library(clpfd)).
:- use_module(library(between)).
bench_(How, N, Ub) :-
   \+ \+ ( length(Xs, N),
           domain(Xs, 1, Ub),
           all_different(Xs),
           Max-Min #= N-1,
           (  How = 0
           ;  How = min_of , max_of( Max, Xs), min_of( Min, Xs)
           ;  How = minimum, maximum(Max, Xs), minimum(Min, Xs)
           ),
           labeling([enum], Xs) ).

... 我们运行以下测试：

为了估计最坏情况下min/max约束的开销：

?- member(How, [0,v1,v2]), call_time(bench_(How,10,10), T_ms). How = 0 , T_ms = 5910 ; How = v1, T_ms = 19560 ; How = v2, T_ms = 7190.

为了衡量在更典型的情况下传播min/max约束的运行时开销：

- between(6, 8, N), NN #= N+N, call_time(bench_(v1,N,NN),T_ms). N = 6, NN = 12, T_ms = 50 ; N = 7, NN = 14, T_ms = 300 ; N = 8, NN = 16, T_ms = 2790.

- between(6, 8, N), NN #= N+N, call_time(bench_(v2,N,NN),T_ms). N = 6, NN = 12, T_ms = 20 ; N = 7, NN = 14, T_ms = 100 ; N = 8, NN = 16, T_ms = 830.

在这两个“用例”中，专业约束提供了令人印象深刻的加速。

注脚1：使用SICStus Prolog版本4.3.2（64位）。 注脚2：答案序列已进行后处理以改善外观。

- repeat