Anonymous user
Non-continuous subsequences: Difference between revisions
m
{{out}}
(jq) |
m ({{out}}) |
||
Line 6:
A ''continuous'' subsequence is one in which no elements are missing between the first and last elements of the subsequence.
Note: Subsequences are defined ''structurally'', not by their contents.
So a sequence ''a,b,c,d'' will always have the same subsequences and continuous subsequences, no matter which values are substituted; it may even be the same value.
'''Task''': Find all non-continuous subsequences for a given sequence. Example: For the sequence ''1,2,3,4'', there are five non-continuous subsequences, namely ''1,3''; ''1,4''; ''2,4''; ''1,3,4'' and ''1,2,4''.
Line 52 ⟶ 53:
end Test_Non_Continuous;</lang>
{{out}}
<pre style="height:30ex;overflow:scroll"> 1 3
Line 120:
# OD # )
END; test non continuous</lang>
{{out}}
<pre>
aeiu
Line 196:
# OD # )
)</lang>
{{out}}
<pre>
iu
Line 275:
NEXT s%
ENDPROC</lang>
{{out}}
<pre>
For [1, 2, 3, 4] non-continuous subsequences are:
Line 324:
);
</lang>
{{out}}
<pre>e n t
e n
Line 523:
}</lang>
{{out}}
<pre>Non-continuous subsequences of 0 1 2 3 4
- 0 2
Line 627:
</lang>
{{out}}
<
> coffee non_contig_subseq.coffee
[ [ 1, 3 ],
Line 645:
for n=9 there are 466 solutions
for n=10 there are 968 solutions
</
=={{header|Common Lisp}}==
Line 808:
masks(length(List))).</lang>
{{out}}
<pre>
Eshell V5.10.1 (abort with ^G)
Line 858:
}
}</lang>
{{out}}
<pre>
5 non-continuous subsequences:
Line 882:
ncsubseq = fenceM [((:), action even), (flip const, action odd)] (>= 3) 0</lang>
{{out}}
<pre>*Main> ncsubseq [1..3]
[[1,3]]
Line 914 ⟶ 913:
nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)</lang>
{{out}}
<pre>
*Main> ncsubs "aaa"
["aa"]
Line 928 ⟶ 927:
[]
(0.00 secs, 0 bytes)
</pre>
A disjointed subsequence is a consecutive subsequence followed by a gap,
then by any nonempty subsequence to its right:
<lang haskell>import Data.List (subsequences, tails, delete)
Line 939 ⟶ 940:
main = print $ length $ disjoint [1..20]</lang>
Build a lexicographic list of consecutive subsequences,
and a list of all subsequences, then subtract one from the other:
<lang haskell>import Data.List (inits, tails)
Line 1,033 ⟶ 1,035:
print(JSON.stringify( non_continuous_subsequences( powerset([1,2,3,4]))));</lang>
{{out}}
<pre>[[1,3],[1,4],[2,4],[1,2,4],[1,3,4]]</pre>
Line 1,103 ⟶ 1,105:
echo "ncsub(", toSeq 1.. 4, ") = ", ncsub(toSeq 1..4)
echo "ncsub(", toSeq 1.. 5, ") = ", ncsub(toSeq 1..5)</lang>
{{out}}
<pre>ncsub(@[1, 2, 3]) = @[@[1, 3]]
ncsub(@[1, 2, 3, 4]) = @[@[1, 2, 4], @[1, 3, 4], @[1, 3], @[1, 4], @[2, 4]]
Line 1,135 ⟶ 1,137:
let ncsubseq = fence 0</lang>
{{out}}
<pre># ncsubseq [1;2;3];;
- : int list list = [[1; 3]]
Line 1,187 ⟶ 1,188:
nonContigSubseq([1,2,3])
nonContigSubseq(["a","b","c","d","e"])</lang>
{{out}}
<pre>[1, 3]
Line 1,239 ⟶ 1,240:
say ~ non_continuous_subsequences( 1..4 )».perl;
say ~ non_continuous_subsequences( ^4 ).map: {[<a b c d>[.list]].perl};</lang>
{{out}}
[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>
Line 1,291 ⟶ 1,293:
ncsubseq([1 2 3 4 5]) =></lang>
{{out}}
<
[2 3 5] [1 2 3 5] [1 4 5] [2 4 5] [1 2 4 5] [1 3 4 5]]</
=={{header|PowerShell}}==
Line 1,414 ⟶ 1,416:
return [[]] if s >= 3 else []</lang>
{{out}}
<pre>>>> ncsub(range(1, 4))
[[1, 3]]
Line 1,548 ⟶ 1,549:
/*──────────────────────────────────S subroutine───────────────────────*/
s: if arg(1)==1 then return ''; return word(arg(2) 's',1) /*plurals.*/</lang>
<pre style="overflow:scroll">
list= 1 2 3 4
Line 1,560 ⟶ 1,561:
5 non-continuous subsequences were found.
</pre>
<pre style="overflow:scroll">
list= a e I o u
Line 1,583 ⟶ 1,584:
16 non-continuous subsequences were found.
</pre>
<pre style="overflow:scroll">
list= Alderney Guernsey Herm Jersey Sark
Line 1,606 ⟶ 1,607:
16 non-continuous subsequences were found.
</pre>
<pre style="overflow:scroll">
list= helium neon argon krypton xenon radon
Line 1,727 ⟶ 1,728:
(recurse (+ s 1) xs)))))))</lang>
{{out}}
<pre>> (ncsubseq '(1 2 3))
((1 3))
Line 1,803:
fun ncsubseq xs = fence 0 xs</lang>
{{out}}
<pre>- ncsubseq [1,2,3];
val it = [[1,3]] : int list list
Line 1,853 ⟶ 1,852:
examples = noncontinuous 'abcde'</lang>
{{out}}
<pre>abce
abd
| |||