增長最長的子集Prolog

Question

我想在Prolog中創建查找輸入列表中最長的子集。例如，您輸入的[3,1,2]列表，輸出爲[1,2]，

?- subset([3,1,2], X). 
X = [1,2] 

我有代碼顯示了這個列表的所有子集：

subset([],[]). 
subset([_|X],Y):-subset(X,Y). 
subset([A|X],[A|Y]):-subset(X,Y). 

任何人都可以幫助我找到最長的增長子集？

Answer 1

你的意思是[1,3,5,6,7]是[4,1,3,8,9,5,6,7]的答案嗎？ IOW，你真的是指子集，還是僅僅是子列表，即列表中的連續部分？

如果是後者，您將不需要子集。搜索是線性的。如果在列表[a,b,c,d,e,f]中發現d > e和增加的序列[a,b,c,d]停止，則不需要立即從b重新開始搜索：序列仍將在d處中斷。您將繼續從e進行搜索。

因此，我們只是在搜索過程中攜帶一些附加信息，當前的和獲勝的子序列。和他們的長度。

longest_incr([],0-[]). 
longest_incr([A|B],RL-R):-     % R is the result, of length RL 
    longest_aux(B,[],0, [A],1, RL-R). 

longest_aux([], Win,N, Curr,K, RL-R):- 
    (K>N -> RL=K, reverse(Curr,R) ; RL=N, reverse(Win,R)). 
longest_aux([A|B],Win,N, Curr,K, RL-R):- Curr = [X|_], L is K, 
    (A>X -> longest_aux(B,Win, N, [A|Curr],L+1,RL-R) % keep adding 
    ; L>N -> longest_aux(B,Curr,K, [A],  1, RL-R) % switch the winner 
    ;  longest_aux(B,Win, N, [A],  1, RL-R) % winner unbeaten 
    ). 

如果OTOH你真的需要最長的子集......那裏就有矛盾。一組可以有它的元素重新排列，所以給定的列表中最長的子集將是

longset_subset(L,R):- sort(L,S), R=S. 

也許你指的是最長的保序子序列，即允許它是不連續的。然後你就可以收集到您的subset所有解決方案findall或類似的斷言，並分析這些結果：

longest_subseq(L,R):- 
    findall(S, subset(L,S), X), 
    maplist(longest_incr, X, Y), 
    keysort(Y, Z), 
    last(Z, _Len-R). 

上面有很多在它的冗餘。我們可以嘗試通過只允許增加子序列，以提高其效率：

incr_subseq([],[]). 
incr_subseq([_|X],Y):- incr_subseq(X,Y). 
incr_subseq([A|X],[A|Y]):- incr_subseq(X,Y), (Y=[] ; Y=[B|_], A<B). 

現在所有由上述謂詞中發現的子序列將越來越大，因此我們就可以把他們的length S：

lenlist(List,Len-List) :- length(List,Len). 
longest_subseq(L,R):- 
    findall(S, incr_subseq(L,S), X), 
    maplist(lenlist, X, Y), 
    keysort(Y, Z), 
    last(Z, _Len-R). 

或者，線性搜索longest_incr可以調整爲更有效的解決方案。它不會只維護一個獲勝的子序列，而是會沿着輸入列表保留所有相關的可能性。

Answer 2

只是出於好奇，那會是在序言中可以實現這樣的尋找最長遞增子：

• 您發現列表
• 的所有子集比你會發現，這些子集是increasing
• 然後你搜索最長

如果有可能，我怎麼能做到這一點的Prolog的？