Longest Decreasing Subsequence 1

[Yarneo]

Hi everyone,
Im trying to code the Longest Decreasing Subsequences out of a given List in prolog.
The problem is is that i get duplicates of the answers.
here is my code:


sublist([],[]).
sublist([X|R],[X|S]):- sublist(R,S).
sublist([_|R],S):- sublist(R,S).

% longest(List,SubList)/2 with mode longest(+,-) : SubList will be instantiated
% to a sublist of List which is decreasing and of maximal length.
longest(List,SubList) :- setof([Len,DecrSub],decreasing_sublist(List,Len,DecrSub),Ye), reverse(Ye,Y),funky(Y,SubList).

funky([X|_],Ans) :- last(X,Ans).
funky([[X,_],[Y,Ys]|Zs],Ans) :- X == Y, funky([[Y,Ys]|Zs],Ans).

decreasing_sublist(List,Len,DecrSub) :-
sublist(List,DecrSub),
sort(DecrSub,DecrSubSorted),
reverse(DecrSubSorted,DecrSub),
length(DecrSub,Len).


this is the output i get:

64 ?- longest([5,7,4,9,3,2,1],SubList).
SubList = [7, 4, 3, 2, 1] ;
SubList = [5, 4, 3, 2, 1] ;
SubList = [7, 4, 3, 2, 1] ;
SubList = [5, 4, 3, 2, 1] ;
false.

65 ?- setof([Len,DecrSub],decreasing_sublist([5,7,4,9,3,2,1],Len,DecrSub),Ye), reverse(Ye,Y),funky(Y,SubList).
Ye = [[0, []], [1, [1]], [1, [2]], [1, [3]], [1, [4]], [1, [5]], [1, [...]], [1|...], [...|...]|...],
Y = [[5, [7, 4, 3, 2, 1]], [5, [5, 4, 3, 2, 1]], [4, [9, 3, 2, 1]], [4, [7, 4, 3|...]], [4, [7, 4|...]], [4, [7|...]], [4, [...|...]], [4|...], [...|...]|...],
SubList = [7, 4, 3, 2, 1] ;
Ye = [[0, []], [1, [1]], [1, [2]], [1, [3]], [1, [4]], [1, [5]], [1, [...]], [1|...], [...|...]|...],
Y = [[5, [7, 4, 3, 2, 1]], [5, [5, 4, 3, 2, 1]], [4, [9, 3, 2, 1]], [4, [7, 4, 3|...]], [4, [7, 4|...]], [4, [7|...]], [4, [...|...]], [4|...], [...|...]|...],
SubList = [5, 4, 3, 2, 1] ;
false.

as you can see in 64:- i get duplicates.
but when i take the line of my code and use it, i dont get duplicates.
does someone know how i can fix this?
thanks so much
Yarden.

 

[kahleen]

Your error resides in funky. It takes a list of pairs [Length, Sublist] sorted by length in decreasing order. So your longest subsequences must be the first in this list. I don't understand why you need to traverse the list of pairs, since you could just take the subsequence from the first pair.

Your current version of funky will produce duplicates if you have consecutive pairs with the same length. These duplicates will also produce duplicates in the predicates that call funky. You can rewrite funky like this (but I'm sure it's not news for you, since you managed to write the rest of the code):

funky([ [_, X] | _], X).

 

[Yarneo]

thanks so much for your reply.
I understand my lack of efficiency on the first line of funky.
But I do want all decreasing subsets. If I remove my second line of funky all i get is one long subsequence and not all the longest ones.
Still, with the new funky, I do get duplicates even for one answer.

39 ?- longest([5,7,4,9,3,2,1],SubList).
SubList = [7, 4, 3, 2, 1] ;
SubList = [7, 4, 3, 2, 1] ;
false.

 

[kahleen]

Ah, so you want all the longest subsequences, from the title of the topic I understood you only needed one of them.

First of all, your initial 'longest' predicate produces only 2 solutions on my version of Prolog, and the version I suggested produces only one. I'm not sure why on your version you get 4 solutions and then 2 solutions.

So if I get it right, funky should extract from the list of pairs the first N subsequences that have the same length. It should produce a list of subsequences, then:

funky([[X, Xs], [Y, Ys] | Zs], [Xs | Ans1]) :-
	X = Y,
	!,
	funky([[Y, Ys] | Zs], Ans1).
funky([[X, Xs], [Y, _] | _], [Xs]) :-
	X \= Y.

How many solutions now? I get this:

?- longest([5, 7, 4, 9, 3, 2, 1], Seq).
Seq = [[7, 4, 3, 2, 1], [5, 4, 3, 2, 1]]

?- longest([5, 7, 8, 4, 9, 3, 2, 1], Seq).
Seq = [[8, 4, 3, 2, 1], [7, 4, 3, 2, 1], [5, 4, 3, 2, 1]]

?- longest([5, 8, 7, 4, 9, 3, 2, 1], Seq).
Seq = [[8, 7, 4, 3, 2, 1]]

 

[kahleen]

Sorry, you need two more clauses for funky, to handle all the particular cases:

funky([[_, X]], [X]).
funky([], []).

 

[Yarneo]

Hey kahleen,
I still get this:
4 ?- longest([5, 7, 4, 9, 3, 2, 1], Seq).
Seq = [[7, 4, 3, 2, 1], [5, 4, 3, 2, 1]] ;
Seq = [[7, 4, 3, 2, 1], [5, 4, 3, 2, 1]].

I use SWI-Prolog as instructed in our course.
Furthermore, the professor insisted we dont use the ! symbol as to his opinion just covers bad coding.

 

[kahleen]

In my opinion, the ! symbol is a powerful way to avoid performing exhaustive testing. Of course, beginners often use it within their code because they notice it helps prevent multiple solutions with the same value. They just put it randomly in their code until the problem disappears. My students do that too and it's something I don't approve since they use it without understanding what they are doing. In no way is it a sign of bad coding if you know what you are doing.

In the example above, the ! is not needed. If I put if after X = Y, then on the next 'funky' clause I don't have to test X \= Y because it's obviously true. But since I seem to have put X \= Y anyway, you can take out the ! symbol safely

I don't know what to say about the two solutions that you obtained. I copied/pasted your code, ran it on my SWI-Prolog and didn't obtain duplicates.

What does Prolog answer to this:
?- funky([ [2, [1, 2]], [2, [1, 2]] ], Result).
Result = [ [1, 2], [1, 2] ]


Try debugging your code to see what happens in there:

Type:
?- guitracer.

You should get a 'true' answer.

Then:

?- trace, longest([5, 7, 4, 9, 3, 2, 1], Seq).

You will enter a graphical debugger where you can step over code lines with the 'Space' key and step into code lines with the 'S' key. Variables will be printed somewhere in the upper left area of the debugger.

If the process is hard to watch, you can use a simpler call (longest([5, 3, 1], Seq) or something similar), or you can debug independently the sublist predicate, the funky predicate and the decreasing_sublist predicate

 

[Yarneo]

First off, thanks for the gui tracer, I didnt know it existed and it certainly helps me alot.
I used it, and it worked fine.
The duplicate I get is when i do the ";" symbol after my first result.
I tried to trace why it backtracks and does it all over and couldnt understand why.
I do think it could be the setof() function but I cant be too sure.
Still is bizarre to me that when I do
setof([Len,DecrSub],decreasing_sublist([5,7,4,9,3,2,1],Len,DecrSub),Ye), reverse(Ye,Y),funky(Y,SubList).
it does not duplicate my answer when i do ";".

 

[kahleen]

If I got some duplicates myself, maybe I could help better, but it works fine for me.

What I would try if I were in your shoes would be to test each part of the 'longest' predicate individually. Test each component by asking the corresponding predicate alone at the Prolog prompt, see which one of them behaves strange. If you get duplicate solutions, it's a good chance that some component of the problem produces duplicate solutions which propagate to the result.

Test them individually as if they were called by Prolog. What does this call return for you?

?- funky( [[1, [1, 2]], [1, [1, 2]]] , Result).

Try more on your own, it's hard for me to help

 

[Yarneo]

hey kahleen,
Ive tried tracing Ive tried every predicate individually. It all looks fine, also each predicate individually returns the result only once. Its only when they are encapsulated by my function it gives duplicates. I also noticed that when I use your funky, and I put an exclamation mark at the end of longest() I dont get duplicates. But as I said im not allowed to use exclamation mark.
Anyway thanks for your help and time I really appreciate it.
Best regards,
Yarden.

 

[kahleen]

If you put a ! at the end of 'longest' and it stops producing duplicates, then this is a strong clue that one of the predicates involved in 'longest' produces duplicates. The ! sign prevents those duplicates from manifesting.

You should try a lot of scenarios to safely assume a predicate is free of duplicates. If you just try 2-3 calling scenarios, your predicate could work fine, but if you tried a 4th way of calling the predicate, it could produce duplicates.

Just out of curiosity and hope it's not annoying for you: what does your version of funky and my version of funky return on your machine if you ask this:

?- funky([ [3, [3, 2, 1]], [3, [4, 3, 2]], [2, [2, 1]], [2, [3, 2]]], Result).

 

[Yarneo]

these are the results I got for funky:
my funky returned:

7 ?- funky([ [3, [3, 2, 1]], [3, [4, 3, 2]], [2, [2, 1]], [2, [3, 2]]], Result).
Result = [3, 2, 1] ;
Result = [4, 3, 2] ;
false.

and yours returned:

58 ?- funky2([ [3, [3, 2, 1]], [3, [4, 3, 2]], [2, [2, 1]], [2, [3, 2]]], Result).
Result = [[3, 2, 1], [4, 3, 2]].

gonna try some more scenarios now, hopefully catch the problem

 

[kahleen]

It's the same on my machine. I hope you didn't have define 'longest' twice or something. That would explain why all the predicates behave correctly when called individually but incorrectly when used in 'longest'. And it would explain why the body of 'longest' also behaves correctly if you write it down at the Prolog prompt.

Please watch your source file carefully and make sure there it nothing like this in there:

longest(List,SubList) :-
	setof([Len,DecrSub],decreasing_sublist(List,Len,DecrSub),Ye),
	reverse(Ye,Y),
	funky(Y,SubList).

... some other code ...
... some comments ...

longest(List,SubList) :-
	setof([Len,DecrSub],decreasing_sublist(List,Len,DecrSub),Ye),
	reverse(Ye,Y),
	funky(Y,SubList).

 

[Yarneo]

I thought of that but it isnt the case, i even changed the predicate name and it did the same thing.
I tried this predicate:

longest22(List,Ye) :- setof([Len,DecrSub],decreasing_sublist(List,Len,DecrSub),Ye).

and this in the command line:
18 ?- longest22([5,7,4,9,3,2,1],SubList).

and i got:
SubList = [[0, []], [1, [1]], [1, [2]], [1, [3]], [1, [4]], [1, [5]], [1, [...]], [1|...], [...|...]|...] ;
SubList = [[0, []], [1, [1]], [1, [2]], [1, [3]], [1, [4]], [1, [5]], [1, [...]], [1|...], [...|...]|...].

so i still think its to do with the setof function, even though as before if i put
setof([Len,DecrSub],decreasing_sublist([5,7,4,9,3,2,1],Len,DecrSub),Ye).
in the command line it gives me just ones answer.

 

[kahleen]

That's odd ... Can you please send me your source file via e-mail? It's just tickling my curiosity as to why this can happen

My e-mail is calin.jebelean@yahoo.co.uk

 

[Yarneo]

Ok I have found the problem!
I dont know why its like that, but when I tried duplicating the function setof() into my file and renamed it to setof2() like this:

longest(List,SubList) :- setof2([Len,DecrSub],decreasing_sublist(List,Len,DecrSub),Ye),reverse(Ye,Y),funky(Y,SubList).

free_variable_set(Templ, Goal0, Goal, Vars) :-
goal_simplified_vars(Goal0, Goal, GoalVars),
'$e_free_variables'(Templ^GoalVars, Vars).

goal_simplified_vars(G0, G, Vars) :-
var(G0), !, G0 = G, G0 = Vars.
goal_simplified_vars(V^G0, G, V^Vars) :- !,
goal_simplified_vars(G0, G, Vars).
goal_simplified_vars(M:G0, M:G, M:Vars) :- !,
goal_simplified_vars(G0, G, Vars).
goal_simplified_vars(G, G, Vars) :-
term_variables(G, Vars).


setof2(Templ, Goal0, List) :-
free_variable_set(Templ, Goal0, Goal, Vars),
( Vars == v
-> findall(Templ, Goal, Answers),
Answers \== [],
sort(Answers, List)
; findall(Vars-Templ, Goal, Answers),
( ground(Answers)
-> sort(Answers,Sorted),
pick(Sorted,Vars,List)
; bind_bagof_keys(Answers,_VDict),
sort(Answers, Sorted),
pick(Sorted, Vars, Listu),
sort(Listu,List) % Listu ordering may be nixed by Vars
)
).

Then it works perfectly with no duplicates!
Oh well