序言 - 寻找最长递增子

对于整数Zs的列表，max_sequence(Zs,Xs)找到一个longest increasing subsequenceXs。

示例查询：

 
?- max_sequence([1,2,1,2,3,4,2,1,2,1],Xs). 
Xs = [1,2,3,4].          % expected result 

?- max_sequence([1,2,1,2,3,4,2,1,6,7,7,2,1,8],Xs). 
Xs = [1,2,3,4,6,7,8].        % expected result

我不明白为什么...但我的代码是错误的，结果总是false。

max_sequence(L,R) :- 
    cresc(L,[],R). 

cresc([],[],[]). 
cresc([H|T],C,[H|C]) :- 
    maxList(H,C), 
    \+ member(H,C), 
    cresc(T,C,C). 
cresc([H|T],C,C) :- 
    member(H,C), 
    cresc(T,C,C).  
cresc([H|T],C,C) :- 
    \+ maxList(H,C), 
    cresc(T,C,C). 

maxList(_,[]). 
maxList(N, [H|T]) :- 
    N>H, 
    maxList(N,T).

我想知道我的方法是否正确。感谢您的帮助！

来源

2015-09-14 JinLemon

你可以用的东西像你'maxList/2'谓词开始。这是什么意思，语义？它的目的是什么？如果'N'大于'L'的每个成员，或者如果'L'是空的，无论如何，它看起来像'maxList（N，L）'成功。这是你的意图吗？那么当'C'没有实例化时，'cresc/2'的第二个子句具有'maxList（H，C）'。这可能是不正确的，我敢打赌你可能会在'>/2'上看到一个实例化错误（尽管你还没有确切地说过你尝试过的例子或者你得到了什么错误）。 – lurker

maxList是你写的内容，检查N是否是那些已经被控制的（C列表中的）最大的数字，并且即使L为空也是成功的。是的，实例化错误是我最初的问题，但更重要的是，似乎我的程序无法正常工作，我不明白为什么（所以我的语义问题）。 – JinLemon

而不是正确的序列（[1,2,3,4]）我只有一个错误 – JinLemon

我根本无法理解您的方法，但在swi-prolog中使用Trace命令，您可以逐步查看程序执行情况，以查看其失败的位置。试试看，你会发现你的代码有什么问题。

不管怎么说，这可能是一个可能的解决方案：从列表中的第一个元素开始，你应该简单地收集列表，直到元素都在增加，也保持此子表的长度，这是第一人选。然后再次开始收集一个新的名单和它的长度，如果比候选人长，你可以切换它们，等等。在这里你可以找到代码：max_seqs，第一部分。

来源

2015-09-15 10:12:24 rok

TL; DR：解决高层次问题：认为地道;并且不要重新发明轮子:)

使用clpfd！

:- use_module(library(clpfd)).

我们继续通过以下两个步骤：

我们开始使用meta-predicate splitlistIfAdj/3连同(#>=)/3：

?- splitlistIfAdj(#>=,[1,2,2,2,1,2,3,4,2,1,3,5,7,1],Zss). 
Zss = [[1,2],[2],[2],[1,2,3,4],[2],[1,3,5,7],[1]].

我们只是在最大的子列表感兴趣尺寸。 max_of_by/3可以排除所有其他的人：

?- max_of_by(Xs,[[1,2],[2],[2],[1,2,3,4],[2],[1,3,5,7],[1]],length). 
    Xs = [1,2,3,4] 
; Xs = [1,3,5,7].

这就是它！让我们把它放在一起，定义list_longest_ascending_sublist/2：

list_longest_ascending_sublist(Xs,Zs) :- 
    splitlistAdjIf(#>=,Xs,Yss), 
    max_of_by(Zs,Yss,length).

示例查询：

 
?- list_longest_ascending_sublist([1,2,2,2,1,2,3,4,2,1,3,5,7,1],Zs). 
    Zs = [1,2,3,4] 
; Zs = [1,3,5,7]. 

?- list_longest_ascending_sublist([1,2,2,3,4,5,6,2,1,2,3,4,2,1,3,5,7,1],Zs). 
Zs = [2,3,4,5,6].

来源

2015-09-15 19:58:51 repeat

非常感谢您的回答，但我的问题有点不同（[1,2,2,2,1,2,3,4,2,1,3,5,7,1]应该回答[1 ，2,3,4,5,7]） – JinLemon

序言 - 寻找最长递增子

回答

相关问题