Rosetta Code

Longest increasing subsequence: Difference between revisions

Page Discussion

Longest increasing subsequence (view source)

Revision as of 04:11, 25 January 2022

9,418 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, marked p2js compatible
(Added JavaScript Patience sorting method)
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 2,016:
=={{header|Phix}}==
Using the Wikipedia algorithm (converted to 1-based indexing)
<!--<lang Phix>(phixonline)-->
<lang Phix>function lis(sequence X, integer N = length(X))
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence P = repeat(0,N)
<span style="color: #008080;">function</span> <span style="color: #000000;">lis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))</span>
sequence M = repeat(0,N)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
integer len = 0
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
for i=1 to N do
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer lo = 1
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
integer hi = len
<span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
while lo<=hi do
<span style="color: #004080;">integer</span> <span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">len</span>
integer mid = ceil((lo+hi)/2)
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
if X[M[mid]]<X[i] then
<span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">((</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">+</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
lo = mid + 1
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]]<</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
hi = mid - 1
end if<span style="color: #008080;">else</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if lo>1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
P[i] = M[lo-1]
<span style="color: #008080;">if</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
M[lo] = i
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if lo>len then len = lo end if
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">></span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lo</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sequence res = repeat(0,len)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if len>0 then
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)</span>
integer k = M[len]
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
for i=len to 1 by -1 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">len</span><span style="color: #0000FF;">]</span>
res[i] = X[k]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">len</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
k = P[k]
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
constant tests = {{3, 2, 6, 4, 5, 1},
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}}
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
for i=1 to length(tests) do
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">}}</span>
?lis(tests[i])
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for</lang>▼
<span style="color: #0000FF;">?</span><span style="color: #000000;">lis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
▲end for<!--</lang>-->
{{out}}
<pre>
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/234604"