How to resolve the algorithm Longest increasing subsequence step by step in the Picat programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Longest increasing subsequence step by step in the Picat programming language

Table of Contents

Problem Statement

Calculate and show here a longest increasing subsequence of the list: And of the list: Note that a list may have more than one subsequence that is of the maximum length.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Longest increasing subsequence step by step in the Picat programming language

Source code in the picat programming language

table(+,+,max)
lis_mode(In, Out,OutLen) =>
  one_is(In, [], Is),
  Out = reverse(Is),
  OutLen = Out.length.

one_is([], Current, Current2) => Current = Current2.
one_is([H|T], Current, Final) =>
	( Current = [], one_is(T, [H], Final));
	( Current = [H1|_], H1 @< H, one_is(T, [H|Current], Final));
	one_is(T, Current, Final).

lis_cp(S, Res,Z) =>
  Len = S.len,
  X = new_list(Len),
  X :: 0..1,

  increasing_except_0($[X[I]*S[I] : I in 1..Len]),
  Z #= sum(X),

  solve($[max(Z)],X),
  % Extract the found LIS
  Res = [S[I] : I in 1..Len, X[I] == 1].

% 
% Ensures that array A is (strictly) increasing if we disregard any 0's
% 
increasing_except_0(A) =>
  N = A.len,
  foreach(I in 1..N, J in I+1..N)
    (A[I] #!= 0 #/\ A[J] #!= 0) #=> (A[I] #< A[J])
  end.

import sat. % for lis_cp
% import cp. % Slower than sat on larger instances.

go =>
  nolog,
  Tests = [
        [3,2,6,4,5,1],
        [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],
        [1,1,1,1],
        [4,65,2,-31,0,99,83,782,1]
       ],
  Funs = [lis_mode, lis_cp],
  
  foreach(Fun in Funs)
    println(fun=Fun),
    foreach(Test in Tests)
       call(Fun,Test,Lis,Len),
       printf("%w: LIS=%w (len=%d)\n",Test, Lis,Len)
    end,
    nl,
  end,
  nl.

  

You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Julia programming language
You may also check:How to resolve the algorithm Bitmap/Read a PPM file step by step in the Wren programming language
You may also check:How to resolve the algorithm Musical scale step by step in the Nanoquery programming language
You may also check:How to resolve the algorithm Sorting algorithms/Radix sort step by step in the Elixir programming language
You may also check:How to resolve the algorithm Haversine formula step by step in the Java programming language