Non-continuous subsequences: Difference between revisions

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.~~

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:

Line 53:

end Test_Non_Continuous;</lang>

Sample output:

<pre style="height:30ex;overflow:scroll"> 1 3

Line 120:

# OD # )

END; test non continuous</lang>

Output:

<pre>

aeiu

Line 196:

# OD # )

)</lang>

Output:

<pre>

iu

Line 275:

NEXT s%

ENDPROC</lang>

'''Output:'''

<pre>

For [1, 2, 3, 4] non-continuous subsequences are:

Line 324:

);

</lang>

Output:

<pre>e n t

e n

Line 523:

}</lang>

Output:

<pre>Non-continuous subsequences of 0 1 2 3 4

- 0 2

Line 627:

</lang>

output

<~~lang~~>

<pre>

> coffee non_contig_subseq.coffee

[ [ 1, 3 ],

Line 645:

for n=9 there are 466 solutions

for n=10 there are 968 solutions

</~~lang~~>

</pre>

=={{header|Common Lisp}}==

Line 808:

masks(length(List))).</lang>

Output:

<pre>

Eshell V5.10.1 (abort with ^G)

Line 858:

}

}</lang>

Output:

<pre>

5 non-continuous subsequences:

Line 882:

ncsubseq = fenceM [((:), action even), (flip const, action odd)] (>= 3) 0</lang>

Output:

<pre>*Main> ncsubseq [1..3]

[[1,3]]

Line 914:

Line 913:

nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)</lang>

Output:

<pre>

*Main> ncsubs "aaa"

["aa"]

Line 928:

Line 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:~~

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:

Line 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:~~

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:

Line 1,035:

print(JSON.stringify( non_continuous_subsequences( powerset([1,2,3,4]))));</lang>

Outputs:

Line 1,103:

Line 1,105:

echo "ncsub(", toSeq 1.. 4, ") = ", ncsub(toSeq 1..4)

echo "ncsub(", toSeq 1.. 5, ") = ", ncsub(toSeq 1..5)</lang>

Output:

<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:

Line 1,137:

let ncsubseq = fence 0</lang>

Output:

<pre># ncsubseq [1;2;3];;

- : int list list = [[1; 3]]

Line 1,187:

Line 1,188:

nonContigSubseq([1,2,3])

nonContigSubseq(["a","b","c","d","e"])</lang>

Output:

<pre>[1, 3]

Line 1,239:

Line 1,240:

say ~ non_continuous_subsequences( 1..4 )».perl;

say ~ non_continuous_subsequences( ^4 ).map: {[<a b c d>[.list]].perl};</lang>

~~Output:~~<pre>[1, 3]

<pre>[1, 3]

[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:

Line 1,293:

ncsubseq([1 2 3 4 5]) =></lang>

Output:

<~~lang pop11~~>[[1 3] [1 4] [2 4] [1 2 4] [1 3 4] [1 5] [2 5] [1 2 5] [3 5] [1 3 5]

<pre>[[1 3] [1 4] [2 4] [1 2 4] [1 3 4] [1 5] [2 5] [1 2 5] [3 5] [1 3 5]

[2 3 5] [1 2 3 5] [1 4 5] [2 4 5] [1 2 4 5] [1 3 4 5]]</~~lang~~>

[2 3 5] [1 2 3 5] [1 4 5] [2 4 5] [1 2 4 5] [1 3 4 5]]</pre>

=={{header|PowerShell}}==

Line 1,414:

Line 1,416:

return [[]] if s >= 3 else []</lang>

Output:

<pre>>>> ncsub(range(1, 4))

[[1, 3]]

Line 1,548:

Line 1,549:

/*──────────────────────────────────S subroutine───────────────────────*/

s: if arg(1)==1 then return ''; return word(arg(2) 's',1) /*plurals.*/</lang>

~~'''output'''~~ when using the input: <tt> 1 2 3 4 </tt>

{{out}} when using the input: <tt> 1 2 3 4 </tt>

list= 1 2 3 4

Line 1,560:

Line 1,561:

5 non-continuous subsequences were found.

</pre>

~~'''output'''~~ when using the following input: <tt> a e I o u </tt>

{{out}} when using the following input: <tt> a e I o u </tt>

list= a e I o u

Line 1,583:

Line 1,584:

16 non-continuous subsequences were found.

</pre>

~~'''output'''~~ when using the [channel Islands (Great Britain)] as input: <tt> Alderney Guernsey Herm Jersey Sark </tt>

{{out}} when using the [channel Islands (Great Britain)] as input: <tt> Alderney Guernsey Herm Jersey Sark </tt>

list= Alderney Guernsey Herm Jersey Sark

Line 1,606:

Line 1,607:

16 non-continuous subsequences were found.

</pre>

~~'''output'''~~ when using the following [six noble gases] as input: <tt> helium neon argon krypton xenon radon </tt>

{{out}} when using the following [six noble gases] as input: <tt> helium neon argon krypton xenon radon </tt>

list= helium neon argon krypton xenon radon

Line 1,727:

Line 1,728:

(recurse (+ s 1) xs)))))))</lang>

Output:

<pre>> (ncsubseq '(1 2 3))

((1 3))

Line 1,803:

fun ncsubseq xs = fence 0 xs</lang>

Output:

<pre>- ncsubseq [1,2,3];

val it = [[1,3]] : int list list

Line 1,853:

Line 1,852:

examples = noncontinuous 'abcde'</lang>

Output:

<pre>abce

abd