Non-continuous subsequences: Difference between revisions
Content added Content deleted
(Added Quackery.) |
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible, some minor simplifications) |
||
Line 1,846: | Line 1,846: | ||
Straightforward recursive implementation, the only minor trick is that a gap does not |
Straightforward recursive implementation, the only minor trick is that a gap does not |
||
mean non-contiguous until you actually take something later.<br> |
mean non-contiguous until you actually take something later.<br> |
||
Counts non-contiguous subsequences of sequences 1..20 in |
Counts non-contiguous subsequences of sequences of length 1..20 in under half a second |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer count = 0 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
procedure ncs(sequence rest, integer ri=0, sequence taken={}, bool contig=false, bool gap=false) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">rest</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">contig</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span> |
|||
if ri>=length(rest) then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">>=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
if contig then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">contig</span> <span style="color: #008080;">then</span> |
|||
if countonly then |
|||
<span style="color: #008080;">if</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
count += 1 |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
else |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">taken</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
else |
|||
<span style="color: #008080;">else</span> |
|||
ri += 1 |
|||
<span style="color: #000000;">ri</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
ncs(rest,ri,taken&rest[ri],gap,gap) |
|||
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">)</span> |
|||
ncs(rest,ri,taken,contig,length(taken)!=0) |
|||
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">contig</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">))</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
ncs({1,2,3}) |
|||
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{})</span> |
|||
?"===" |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span> |
|||
ncs({1,2,3,4}) |
|||
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{})</span> |
|||
?"===" |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span> |
|||
countonly = true |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
sequence s = {} |
|||
<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;">20</span> <span style="color: #008080;">do</span> |
|||
for i=1 to 20 do |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
count = 0 |
|||
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
ncs(tagset(i)) |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span> |
|||
s = append(s,count) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
?time()-t0 |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,890: | Line 1,891: | ||
{2,4} |
{2,4} |
||
"===" |
"===" |
||
0. |
"0.3s" |
||
{0,0,1,5,16,42,99,219,466,968,1981,4017,8100,16278,32647,65399,130918,261972,524097,1048365} |
{0,0,1,5,16,42,99,219,466,968,1981,4017,8100,16278,32647,65399,130918,261972,524097,1048365} |
||
</pre> |
</pre> |