使用CLP获取间隔

Question

我希望在prolog环境中获得变量域的非终止间隔。

例如，我有一个变量X，它被限制在它的域中接受一些值。假设X有一个初始域[0..20]，并且它被限制为(不)以5、8、9作为值。所以X有了新的域[0..4, 6, 7, 10..20]。我想得到非停止的时间间隔在这个领域作为一个列表[[0..4], [6,7], [10..20]]。

在SWI中，在运行以下目标时使用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规则解析以L1..U1\/L2..U2\/...形式存在的域。

在SWI手册(链接)中给出了将域作为整数列表的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 手册中没有提到clpfd，但是也可以对YAP进行同样的操作。