Geek Answers Handbook

Largest Prolog Subset

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

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

I have a code that shows all subsets of this list:

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

Can someone help me find only the longest increasing subset?

+1
source share
2 answers

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

If so, you will not need subsets. The search is linear. If in the list [a,b,c,d,e,f] you find that d > e and the increasing sequence [a,b,c,d] stops, now you do not need to restart the search from b : the sequence will still be broken into d . You just continue your search with e .

So, we just carry additional information during the search, namely. current and winning so-called subsequences. 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 is a contradiction. Elements can be rearranged in a set, so the longest subset of this list will be

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

Perhaps you mean the longest subsequence that preserves order, that is, it is allowed to be non-contiguous. Then you can collect all the solutions for your subset using findall or a 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. We can try to increase its effectiveness only by increasing the subsequence:

 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 subsequences found by the above predicate will increase, so we can just take their length s:

 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 search longest_incr can be changed for a more efficient solution. Instead of supporting only one winning subsequence, it will support all the relevant features as it goes along the input list.

+1
source

Just out of curiosity, is it possible in the prolog to implement something like this to search for the longest growing subsequence:

  • You will find all subsets of the list.
  • How do you find which of these subsets is increasing
  • And then you look for the longest

If possible, how can I do this in Prolog?

0
source

More articles:


All Articles