使用 CLP 获取间隔

Question

我想在序言环境中获取可变域的非中断间隔。

例如，我有一个变量 X，它被限制在其域中取一些值。假设 X 有一个 初始域 [0..20] 并且它被限制为（不）具有 5、8、9 作为值.所以 X 有新域 [0..4, 6, 7, 10..20]。我想在这个域中获得非中断间隔作为列表 [[0..4], [6,7], [10..20]]。

在SWI-Prolog中，当我运行以下目标时使用clpfd库：

X in 0..20, X #\= 5, X #\= 8, X #\= 9.

答案是：

X in 0..4\/6..7\/10..20.

到目前为止一切顺利。但我不知道如何将这个域作为间隔列表获取。有办法吗？

也欢迎使用其他 Prolog 实现及其各自的 CLP/FD 库的解决方案。

Answer 1

使用fd_dom/2，可以获得变量的定义域。然后 DCG rule 可用于解析形式为 L1..U1\/L2..U2\/... 的域。

SWI-Prolog 手册 (link) 中给出了将域作为整数列表获取域的示例 DCG 规则。稍加修改就可以用来获取间隔：

dom_intervals(Dom, Intervals) :- phrase(dom_intervals1(Dom), Intervals).

dom_intervals1(I)           -->  {integer(I)}, [I].
dom_intervals1(L..U)        --> [L..U].
dom_intervals1(D1 \/ D2)    --> dom_intervals1(D1), dom_intervals1(D2).

终于可以使用这个查询了：

X in 0..20, X #\= 5, X #\= 8, X #\= 9, fd_dom(X, D), dom_intervals(D, Intervals).

虽然在 YAP-prolog manual 中没有提到 clpfd，但也可以用 YAP-prolog 做同样的事情。

使用 CLP 获取间隔

Getting intervals with CLP

prolog

clpfd