Question

I have list of integers, I need to find the longest subset of ascending integers from the list. For example: [1,2,5,3,6,7,4] - longest subset would have been 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 ).

我并不十分熟悉道歉,因此它带有一种血清法。

我们现在有2个基点:longest Subseq/2和longest Subseq/4。

有一个缓冲(目前是单质的分离),时间最长(目前是最长的次长)和一个蓄水器。

在某些行为中,我们需要处理:

Buffer is empty. We put new element in it.
New element is smaller than last buffer element. We put that element in buffer.
New element is larger than last buffer element. We clear buffer and put that element in it. If buffer was larger than longest subsequence, we substitute it.

因此,这似乎是可行的。

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

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

Answer 2

收回最后一项内容,检查命令。 element element element passed ;

Answer 3

3. 最佳搜索方法:

% not very tested!

longest(L, S) :-
        length(L, Len),
        advance(L, Len, [], [], S).

cmp_start([], _).
cmp_start([H|_], E) :- H =< E. 

add_to_bag([], P, [P]).
add_to_bag([H|T], P, Bag) :-
        P = LenP-_,
        H = LenH-_,
        (   LenH > LenP
        ->  Bag = [H|Bag1],
            add_to_bag(T, P, Bag1)
        ;   Bag = [P, H| T] ).

advance([Len-Start/Tail|Bag], Solution) :-
        advance(Tail, Len, Start, Bag, Solution).

advance([], _, Start, _, Solution) :-
        reverse(Start, Solution).

advance([H|Tail], Len, Start, Bag, Solution) :-
        Len1 is Len - 1,
        add_to_bag(Bag, Len1-Start/Tail, Bag1),
        (   cmp_start(Start, H)
        ->  advance(Tail, Len, [H|Start], Bag1, Solution)
        ;   advance(Bag1, Solution) ).

部分解决办法作为<代码>。 MaximunLength-StartList/ListOfItems ToBeConsidered 。

友情链接