3

我希望能够获取一个数字列表并获得最大的有序数字序列。例如：

?- in_order([1,2,3,4,5],N).
N = 5.                              % expected result

?- in_order([1,2,5,6,7,8,4],N).
N = 4.                              % expected result

到目前为止，我已经生成了一些基本代码来计算数字序列的长度，但是一旦列表为空，它就会回溯，因此返回的数字 N 与列表中的第一个元素相同。我知道我需要停止回溯，但似乎无法做到。有人会很好地指出我正确的方向吗？

到目前为止我的代码（虽然有点老套）：

in_order([],_) :-
   !.
in_order([H|T],N):-
   (  var(N), 
      N is H 
   ;  true
   ),
   H = N,
   M is N+1,
   in_order(T,M).

我确实知道我当前的解决方案在给出的第二个示例中不起作用，并且该方面的指针将再次有帮助，因为我不太确定如何解决该方面。我正在使用 SICStus Prolog。

提前谢谢了！

4

4 回答 4

2

让我称之为关系zs_maxInOrder/2，它基于clpfd 并使用具体化约束：

:- use_module(library(clpfd)).

zs_maxInOrder([]    ,0).
zs_maxInOrder([Z|Zs],N) :-
    zs_prev_n_max0_max(Zs,Z,1,1,N).            % use "lagging" 

zs_prev_n_max0_max([]     ,_ ,_ ,M ,M).
zs_prev_n_max0_max([Z1|Zs],Z0,N0,M0,M) :-
    Z1 #= Z0 + 1 #<=> B,                       % with SWI-Prolog use `(#<==>)/2`
    N1 #= N0 * B + 1,
    M1 #= max(M0,N1),
    zs_prev_n_max0_max(Zs,Z1,N1,M1,M).

让我们使用 SICStus Prolog 4.3.1 来看看它的实际效果：

?- zs_maxInOrder([ 1,2,3,4,5 ],N)。
N = 5 ? ;
不
?- zs_maxInOrder([1,2, 5,6,7,8 ,4],N)。
N = 4 ? ;
不

角落案例呢？

?- zs_maxInOrder([1],N).
N = 1 ? ;
no
?- zs_maxInOrder([],N).
N = 0 ? ;
no
于 2015-04-25T17:23:11.353 回答
1

你的尝试失败了，因为你混合了不同的东西。当你写

N is H

您基本上是在输出列表的元素之一。这是你在任何情况下都不想做的事情。基本情况也是错误的，它应该是“一个空列表的有序序列为零”。

尝试使用“累加器”参数来跟踪以当前头 H 终止的连续元素。

于 2012-12-04T17:10:03.750 回答
1

这是该问题的一个相当强力的解决方案：P（我知道我会受到批评，但我无法抗拒使用高阶谓词）。

my_prefix(List,Prefix) :- 
   append(Prefix,_,List).

my_suffix(List,Suffix) :- 
   append(_,Suffix,List).

my_sublist(List,Sublist) :-
   my_suffix(List,Suffix),
   my_prefix(Suffix,Sublist).

all_sublists(List,AllSublists) :- 
   findall(Sub,my_sublist(List,Sub),AllSublists).

good_list([]) :- 
   !.
good_list([H]) :- 
   !.
good_list([H1,H2|T]) :- 
   H1 is H2-1,
   good_list([H2|T]),
   !.

in_order(List,Length) :-
   all_sublists(List,AllSublists),
   findall(L,(member(Sublist,AllSublists),
              good_list(Sublist),
              length(Sublist,L)),
             InOrderSizes),
   max_list(InOrderSizes,Length).
于 2012-12-04T20:44:58.790 回答
0

“一个空列表的有序序列为零”。

感谢那。它让我走上了正确的轨道（我认为）

到目前为止，这是我的解决方案：

in_order([], _, 0).
in_order([H|T], Prev, N):-
  % Split the list
  in_order(T, H, M),
  % Increment the expected Head value
  H1 is Prev + 1,
    (
      H = H1,
      N is M + 1
    ;
      M1 is M + 1,
      format('M1 is ~w~n', [M1]),
      N is 0
  ).

我添加了格式，以便我可以看到在最后阶段打印的内容，并且我得到了输入 [1,2,5,6,7,8,4] 的值 1 和 4 - 这是正确的。谓词返回 2（序列的最后一个长度），但是当我回溯以尝试获得更多答案时，我没有得到值 4 或 1。我认为我非常接近答案，任何额外的最终帮助都是赞赏。

非常感谢

于 2012-12-05T13:27:18.640 回答