prolog - gprolog 最长子集

Question

我有一个整数列表，我需要从列表中找到升序整数的最长子集。例如:[1,2,5,3,6,7,4] - 最长的子集应该是 SS = [1,2,3,6,7]。

谁能至少告诉我实现它的主要指南。

Answer 1

longestSubseq( List, Ans ) :-
    longestSubseq( List, [], [], Ans ).

longestSubseq( [], Buffer, [], Buffer ) :- !.

longestSubseq( [], _, AnsRevert, Ans ) :-
    reverse( AnsRevert, Ans ).

longestSubseq( [H | Tail], [], Longest, Ans ) :-
    longestSubseq( Tail, [H], Longest, Ans ).

longestSubseq( [H | Tail], [BufHead | BufTail], Longest, Ans ) :-
    BufHead =< H,
    longestSubseq( Tail, [H, BufHead | BufTail], Longest, Ans ).

longestSubseq( [H | Tail], Buffer, Longest, Ans ) :-
    [BufHead | _ ] = Buffer,
    BufHead > H,
    length( Longest, LongestLength ),
    length( Buffer, BufferLength ),
    ( 
        ( BufferLength > LongestLength, NewLongest = Buffer )
    ;
        ( BufferLength =< LongestLength, NewLongest = Longest ) 
    ),
    longestSubseq( Tail, [H], NewLongest, Ans ).

我对 gprolog 不是很熟悉，所以它是一个 swi-prolog 代码。

我们得到的是 2 个谓词:longestSubseq/2 和 longestSubseq/4。

longestSubseq/4 有一个缓冲区(当前单调子序列)，最长(当前时间最长的子序列)和一个累加器 Ans。

我们需要在该累加器中处理一些行为:

1. 缓冲区为空。我们在其中添加了新元素。
2. 新元素小于最后一个缓冲区元素。我们将该元素放入缓冲区。
3. 新元素大于最后一个缓冲区元素。我们清除缓冲区并将该元素放入其中。如果缓冲区大于最长的子序列，我们将替换它。

所以，这似乎是可行的。

?- longestSubseq( [2], X ).
X = [2] ;
false.

?- longestSubseq( [2,1,2,3,2], X ).
X = [1, 2, 3] ;
false.