Longest increasing subsequence: Difference between revisions
→{{header|Picat}}
Drkameleon (talk | contribs) (Added Arturo implementation) |
|||
Line 2,152:
[5] => 15
)</pre>
=={{header|Picat}}==
Two methods:
* mode directed tabling: lis_mode/3 (Inspired by the Prolog version)
* constraint modelling: lis_cp/3. (For larger instances, the sat solver is generally faster than the cp solver.)
The mode directed tabling tends to be the fastest of the two methods.
<lang Picat>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.
%
% Mode directed tabling (inspired by the Prolog version)
%
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).
%
% Constraint modelling approach.
%
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.</lang>
Both outputs:
<pre>[3,2,6,4,5,1]: LIS=[3,4,5] (len=3)
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]: LIS=[0,4,6,9,13,15] (len=6)
[1,1,1,1]: LIS=[1] (len=1)
[4,65,2,-31,0,99,83,782,1]: LIS=[4,65,99,782] (len=4)</pre>
=={{header|PicoLisp}}==
| |||