Longest increasing subsequence: Difference between revisions
→{{header|Picat}}: Split into subsections. Added {{out}}
(→{{header|Picat}}: Split into subsections. Added {{out}}) |
|||
Line 2,154:
=={{header|Picat}}==
===Mode-directed tabling===
{{trans|Prolog}}
<lang Picat>table(+,+,max)▼
* 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.▼
▲table(+,+,max)
lis_mode(In, Out,OutLen) =>
one_is(In, [], Is),
Line 2,197 ⟶ 2,166:
( Current = [], one_is(T, [H], Final));
( Current = [H1|_], H1 @< H, one_is(T, [H|Current], Final));
one_is(T, Current, Final).</lang>
▲
▲% Constraint modelling approach.
<lang Picat>lis_cp(S, Res,Z) =>▼
▲lis_cp(S, Res,Z) =>
Len = S.len,
X = new_list(Len),
Line 2,223 ⟶ 2,191:
end.</lang>
===Test===
▲<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.</lang>
{{out}}
<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)
Line 2,229 ⟶ 2,221:
[4,65,2,-31,0,99,83,782,1]: LIS=[4,65,99,782] (len=4)</pre>
▲The mode directed tabling tends to be the fastest of the two methods.
=={{header|PicoLisp}}==
| |||