Non-continuous subsequences: Difference between revisions
→{{header|Phix}}
m (added whitespace, used a vertical list instead of a horizontal list (for the named example list).) |
|||
Line 1,447:
((1 3) (1 4) (2 4) (1 2 4) (1 3 4))
([a c] [a d] [b d] [a b d] [a c d])</pre>
=={{header|Phix}}==
Straightforward recursive implementation, the only minor trick is that a gap does not
mean non-contiguous until you actually take something later.<br>
Counts non-contiguous subsequences of sequences 1..20 in just over 0.5 seconds
<lang Phix>bool countonly = false
integer count = 0
procedure ncs(sequence rest, integer ri=0, sequence taken={}, bool contig=false, bool gap=false)
if ri>=length(rest) then
if contig then
if countonly then
count += 1
else
?taken
end if
end if
else
ri += 1
ncs(rest,ri,taken&rest[ri],gap,gap)
ncs(rest,ri,taken,contig,length(taken)!=0)
end if
end procedure
ncs({1,2,3})
?"==="
ncs({1,2,3,4})
?"==="
countonly = true
atom t0 = time()
sequence s = {}
for i=1 to 20 do
count = 0
ncs(tagset(i))
s = append(s,count)
end for
?time()-t0
?s</lang>
{{out}}
<pre>
{1,3}
"==="
{1,2,4}
{1,3,4}
{1,3}
{1,4}
{2,4}
"==="
0.515
{0,0,1,5,16,42,99,219,466,968,1981,4017,8100,16278,32647,65399,130918,261972,524097,1048365}
</pre>
=={{header|PicoLisp}}==
| |||