Prolog 约束编程查找偶数和奇数 [英] Prolog Constraint Programing finding even and odd numbers

问题描述

我需要创建一个谓词:

applyConstraints(L)

这将约束应用于 L 中的变量，使得 L 中没有两个连续的元素都是奇数或者偶数，我该怎么做?使用固定大小的 L 很简单，但是可变大小的 L 呢?我需要使用 sicstus-prolog clpfd 库来完成.

That applies constraints to the variables in L such that no two contiguous elements in L are both odd or even how can I do that? With a fixed size L it's simple but what about a variable size L? I need that to be done using sicstus-prolog clpfd library.

推荐答案

受到@MatsCarlsson 版本的启发，我尝试尽量减少所涉及的约束变量的数量:

Inspired by @MatsCarlsson's version, I tried to minimize the number of constrained variables involved:

applyConstraints(Xs) :-
   S #\= R,
   applyConstraints(Xs, S, R).

applyConstraints([], _, _).
applyConstraints([X|Xs], S, R) :-
   X mod 2 #= S,
   applyConstraints(Xs, R, S).

此版本对于目标 applyConstraints([]) 有一个缺陷，该缺陷不易被发现.事实上，需要像这样在 SICStus 中切换到 full_answer 模式:

This version has one flaw for the goal applyConstraints([]) which is not readily visible. In fact, one needs to switch to full_answer mode in SICStus like so:

| ?- applyConstraints([]).
yes
| ?- assertz(clpfd:full_answer).
yes
| ?- applyConstraints([]).
clpfd:(_A#\=_B),
_A in inf..sup,
_B in inf..sup ? ;
no

所以我们有这个无用的约束，它可能会消耗资源.为了克服这个缺陷，需要一些特殊的外壳:

So we have this useless constraint hanging around which might eat up resources. To overcome this deficiency, some special casing is needed:

applyConstraints([]).
applyConstraints([X|Xs]) :-
   X mod 2 #= S,
   S #\= R,
   applyConstraints(Xs, R, S).

注意 1 —在SWI 或 YAP 中，没有直接打开完整应答模式的方法.解决问题的唯一方法是将查询包裹在 call_residue_vars/2 中，如下所示:

Note 1 — in SWI or YAP there is no direct way to switch full answer mode on. The only way to get hold of the problem is to wrap the query around call_residue_vars/2 like so:

?- applyConstraints([]).
true.

?- call_residue_vars(applyConstraints([]),RVs).
RVs = [_G794, _G797],
_G794#\=_G797.

注意 2 —感谢@mat，自 SWI 7.3 起有类似的功能(请记住，SWI 7 需要 --traditional 以实现兼容性):

Note 2 — Thanks to @mat, there is similar functionality since SWI 7.3 (remember that SWI 7 needs --traditional for compatibility):

?- set_prolog_flag(toplevel_residue_vars, true).
true.

?- applyConstraints([]).
% with detached residual goals
_G430#\=_G433.

(在这种情况下，分离"应该是什么意思不是很清楚，毕竟剩余目标必须为真，使答案为真.所以不涉及分离.)

(It is not quite clear what "detached" should mean in this context, after all, the residual goals have to be true, to make the answer true. So there is no detachement involved.)

这篇关于Prolog 约束编程查找偶数和奇数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！