如何检查两个列表整数之间的差异是否大于或等于 2？

Question

给定两个排序列表 Xs 和 Ys，我如何确保 Xs 中的任何 X 与 Y 中的任何 Y 之间的绝对差异=13=]至少是两个？

带有预期答案的示例查询：

?- different([1,2,4],[5,6]).   % 5-4 < 2
false
?- different([1,4],[2,6]).     % 2-1 < 2
false
?- different([1,2,6],[4,8]).   % 4-2 >= 2 and 6-4 >= 2 and 8-6 >= 2
true
?- different([],[4]). 
true

我怎样才能得到这个结果？有任何想法吗？谢谢！

编辑：这是我现在的代码：

difference([], []).
difference([_|_], []).
difference([], [_|_]).
difference(L1, L2) :-
   L1 = [X1|X2],
   L2 = [Y1|_],
   Dif is X1-Y1,
   (-1>Dif|Dif>1),
   difference(X2, L2).

Answer 1

首先，您可以按如下方式使当前代码更整洁、更易于阅读：

different([], []).
different([_|_], []).
different([], [_|_]).
different([X|Xs], [Y|Ys]) :-
    abs(X-Y) >= 2,     % Prolog evaluates arithmetic expressions for compares
    different(Xs, [Y|Ys]).

在这种情况下，您已经完成了我在评论中提到的一级递归，因为它只检查第一个列表的每个元素与第二个列表的第一个元素。它忽略第二个列表的所有其他元素。所以你需要进一步分解它。您可以制作一个辅助谓词，将列表的每个元素与单个值进行比较。然后让您的主谓词使用另一个列表的每个元素调用此辅助谓词。主谓词将如下所示：

different([], []).
different([], [_|_]).
different([X|Xs], L) :-
    different_element(X, L),
    different(Xs, L).

那么辅助谓词将是：

% This predicate succeeds if the first argument has the desired difference
% to each of the elements of the second argument (a list)
%
different_element(_, []).
different_element(X, [Y|Ys]) :-
    abs(X-Y) >= 2,
    different_element(X, Ys).

Answer 2

在这个答案中，我们使用 clpfd 来获得两者多功能性和最佳（线性）算术复杂度。

diff_to_mdist([], _, _).
diff_to_mdist([_|_], [], _).
diff_to_mdist([X|Xs], [Y|Ys], D) :-
   (  X #=< Y-D,            diff_to_mdist(Xs, [Y|Ys], D)
   ;  X #>  Y-D, X #>= Y+D, diff_to_mdist([X|Xs], Ys, D)
   ).
diff_to_mdist([X0,X1|Xs], [Y0,Y1|Ys], D) :-
   X0 #> Y0-D, X0 #< Y0+D,
   (  X0 #< Y0, X0 #=< Y0-D, X1 #>= Y0+D, diff_to_mdist([X0,X1|Xs], [Y1|Ys], D)
   ;  X0 #> Y0, Y0 #=< X0-D, Y1 #>= X0+D, diff_to_mdist([X1|Xs], [Y0,Y1|Ys], D)
   ).

让我们使用 gnu-prolog 版本 1.4.4 和运行查询，就像 OP 建议的那样！

| ?- diff_to_mdist([1,2,4], [5,6], 2).
no
| ?- diff_to_mdist([1,4], [2,6], 2).
no
| ?- diff_to_mdist([1,2,6], [4,8], 2). 
true ? ;
no
| ?- diff_to_mdist([], [4], 2). 
yes

如何检查两个列表整数之间的差异是否大于或等于 2？

How to check different between two list integers are greater than or equal to 2?

list

prolog

clpfd