序言 - 尋找最長遞增子

對於整數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

序言 - 尋找最長遞增子

回答

相關問題