Prolog - Finding the longest increasing subsequence

Question

I want to solve the following exercise in Prolog:

For a list of integers Zs, max_sequence(Zs,Xs) finds a longest increasing subsequence Xs.

Sample queries:

?- max_sequence([1,2,1,2,3,4,2,1,2,1],Xs).
Xs = [1,2,3,4].                                     % expected result

?- max_sequence([1,2,1,2,3,4,2,1,6,7,7,2,1,8],Xs).
Xs = [1,2,3,4,6,7,8].                               % expected result

I can't understand why... but my code is wrong, the result is always false.

max_sequence(L,R) :-
    cresc(L,[],R).

cresc([],[],[]).
cresc([H|T],C,[H|C]) :-
    maxList(H,C),
    \+ member(H,C),
    cresc(T,C,C).
cresc([H|T],C,C) :-
    member(H,C),
    cresc(T,C,C).       
cresc([H|T],C,C) :-
    \+ maxList(H,C),
    cresc(T,C,C).   

maxList(_,[]).
maxList(N, [H|T]) :-
    N>H,
    maxList(N,T).

I would like to know if my approach to the problem is correct. Thanks for any help!

You can start with things like your `maxList/2` predicate. What does it mean, semantically? What's its purpose? It looks to me like `maxList(N, L)` succeeds if `N` is greater than every member of `L`, or if `L` is empty regardless. Is that your intention? Then your second clause for `cresc/2` has `maxList(H, C)` when `C` is not instantiated. That's probably incorrect, and I'll bet you might be seeing an instantiation error on `>/2` (although you haven't said exactly what example you've tried or what error you're getting). — lurker, Sep 14 '15 at 14:09
maxList is what you wrote, checks if N is the biggest number among those already controlled (in C list) and succeds even if L is empty. Yeah the instantiation error was my initial problem, but more than anything else it seems that my program doesn't work as I want, and I can't understand why (so mine is a semantic problem). — JinLemon, Sep 14 '15 at 16:31
Instead of the right sequence ([1,2,3,4]) I have only a false — JinLemon, Sep 14 '15 at 16:33
You should edit your problem and show your updated code with the instantiation error fixed. — lurker, Sep 14 '15 at 16:48
And by "sequence" you mean "subsequence", and by "max" you mean "longest"? (Guessing from the example you give) If you gave your question a correct name it might attract the correct kind of attention. — , Sep 15 '15 at 09:51

score 3 · Answer 1 · edited May 23 '17 at 12:14

TL;DR: Solve problems on a high-level: Think idiomatically; and don't reinvent the wheel :)

Use clpfd!

:- use_module(library(clpfd)).

We proceed by taking the following two steps:

We start by using the meta-predicate splitlistIfAdj/3 together with (#>=)/3:

?- splitlistIfAdj(#>=,[1,2,2,2,1,2,3,4,2,1,3,5,7,1],Zss).
Zss = [[1,2],[2],[2],[1,2,3,4],[2],[1,3,5,7],[1]].

We are only interested in sublists of maximum size. max_of_by/3 can exclude all other ones:

?- max_of_by(Xs,[[1,2],[2],[2],[1,2,3,4],[2],[1,3,5,7],[1]],length).
  Xs = [1,2,3,4]
; Xs = [1,3,5,7].

That's it! Let's put it together and define list_longest_ascending_sublist/2:

list_longest_ascending_sublist(Xs,Zs) :-
   splitlistAdjIf(#>=,Xs,Yss),
   max_of_by(Zs,Yss,length).

Sample queries:

?- list_longest_ascending_sublist([1,2,2,2,1,2,3,4,2,1,3,5,7,1],Zs).
  Zs = [1,2,3,4]
; Zs = [1,3,5,7].

?- list_longest_ascending_sublist([1,2,2,3,4,5,6,2,1,2,3,4,2,1,3,5,7,1],Zs).
Zs = [2,3,4,5,6].

Thank you very much for your answer, but my problem was a little different ([1,2,2,2,1,2,3,4,2,1,3,5,7,1] should answers [1,2,3,4,5,7]) — JinLemon, Sep 27 '15 at 08:48

score 0 · Accepted Answer · edited May 23 '17 at 12:14

I can't understand your approach at all, but using Trace command in swi-prolog you can see your program execution step by step to see where it fails. Try it and you will see what's wrong with your code.

Anyway this could be one possible solution: starting from the first element of the list you should simply collect a list until elements are increasing, keeping also the length of this sublist, this is the first candidate. Then start again collecting a new list and its length, and if is longer than the candidate, you switch them, and so on.. Here you can find the code: max_seqs , the first part.

Prolog - Finding the longest increasing subsequence

2 Answers2