Longest increasing subset Prolog

I want to create in Prolog to find longest increasing subset of entered list. For example, you enter list of [3,1,2] and the output is [1,2],

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

I have code which shows all the subsets of this list:

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

Can anyone help me to find just the longest increasing subset?

回答1:

Do you mean [1,3,5,6,7] to be the answer for [4,1,3,8,9,5,6,7]? IOW, do you really mean subsets, or just sublists, i.e. contiguous portions of the list?

If the latter is the case, you won't need subsets. The search is linear. If in a list [a,b,c,d,e,f] you find that d > e and the increasing sequence [a,b,c,d] stops, you don't need to restart the search from b now: the sequence will still break at d. You will just continue your search from e.

So, we'll just carry around some additional information during the search, viz. the current and the winning-so-far sub-sequences. And their lengths.

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 
    ).

If OTOH you really need the longest subset ... there's a contradiction there. A set can have its elements rearranged, so the longest subset of a given list will be

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

Perhaps you mean the longest order-preserving sub-sequence, i.e. it is allowed to be non-contiguous. Then you can gather all solutions to your subset with findall or similar predicate, and analyze these results:

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

The above has a lot of redundancy in it. We can attempt to improve its efficiency by only allowing the increasing subsequences:

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).

Now all the sub-sequences found by the above predicate will be increasing, so we can just take their lengths:

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).

Or, the linear searching longest_incr could be tweaked for a more efficient solution. Instead of maintaining just one winning sub-sequence, it would maintain all the relevant possibilities as it goes along the input list.

回答2:

Just out of curiosity, would it be possible in prolog to realize something like this for finding longest increasing subsequence: