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.

Answer 2

Лучший подход поиска:

% 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/ListOfItemsToBeConsidered.

Answer 3

Рекурсировать прохождение последнего увиденного элемента, чтобы проверить порядок. Сбой, как только переданный элемент> = текущая голова.