在子列表列表中找到最大间隔（这些子列表有 2 个元素）

Question

我有这个练习，我得到了一个子列表列表，比如 [[X1,Y1],[X2,Y2]...] 代表一个区间 (Xi-Yi)，我想 return 最大区间列表（可以超过一个区间）。

这就是我目前所知道的。我看不出我做错了什么但是当尝试运行 biggest_interval([[1,2],[5,7],[6,10],[12,15]],升）。我得到 true，然后是 false 而不是 [6,10]

biggest_interval([H|T],Answer):-
biggest_interval(H,T,-1,Answer).

biggest_interval([],_,_,_).
biggest_interval(_,[],_,_).

biggest_interval([X,Y],[H|T],Biggest,Answer):-
Z is Y-X,
Z =:= Biggest,
append(Answer,[X,Y],L),
!,
biggest_interval(H,T,Biggest,L).
biggest_interval([X,Y],[H|T],Biggest,Answer):-
Z is Y-X,
(
    Z > Biggest -> append([],[X,Y],L),
    biggest_interval(H,T,Z,L);
    true 
),
biggest_interval(H,T,Biggest,Answer).

Answer 1

您的代码的一个问题是您的谓词 biggest_interval/4 没有收集“基本情况”中的答案（它只会停止递归过程）。

一个可能的解决方案是：

biggest_interval(ListOfLists, Answer) :-
    biggest_interval(ListOfLists, -inf, [], Biggest),
    reverse(Biggest, Answer).   % if order of the pairs is important!


biggest_interval([], _, Answer, Answer) :- !.       % collect Answer!

biggest_interval([[X,Y]|Lists], Max, Acc, Answer) :-
    Z is Y-X,
    (   Z = Max ->  biggest_interval(Lists, Max, [[X,Y]|Acc], Answer)
    ;   Z > Max ->  biggest_interval(Lists,  Z,  [[X,Y]],     Answer)
    ;               biggest_interval(Lists, Max, Acc,         Answer) ).

这里有一些例子：

?- biggest_interval([[1,2],[5,7],[6,10],[12,15]],L).
L = [[6, 10]].

?- biggest_interval([[1,20],[5,7],[6,10],[12,15]],L).
L = [[1, 20]].

?- biggest_interval([[1,2],[5,7],[6,10],[12,15],[3,10]],L).
L = [[3, 10]].

?- biggest_interval([[1,2],[5,7],[6,10],[12,15],[8,12]],L).
L = [[6, 10], [8, 12]].

Answer 2

这是另一种方法，功能设计：

:- use_module(library(lambda)).

biggest_interval([[H1, H2]|T], Out) :-
    D1 is H2 - H1,
    foldl(\X^Y^Z^(X = [A,B],
                  D is B - A,
                  Y = [Delta, L],
                  (   Delta > D
                  ->  Z = Y
                  ;   (   Delta = D
                      ->  append(L, [X], NL),
                          Z = [Delta, NL]
                      ;   Z = [D, [X]]))), T, [D1, [[H1,H2]]], [_, Out]).

示例：

?- biggest_interval([[1,2],[5,7],[6,10],[12,15]],L).
L = [[6, 10]].

?- biggest_interval([[1,2],[5,7],[6,10],[12,15],[8,12]],L).
L = [[6, 10], [8, 12]].

在子列表列表中找到最大间隔（这些子列表有 2 个元素）

find biggest interval in a list of sublists (these sublists have 2 elements)

prolog