Non-continuous subsequences: Difference between revisions

Line 295:

Here, solution sequences are calculated abstractly by <tt>ncs</tt>, then used by <tt>ncs_of</tt> to draw items from the input list.

The algorithm is filtered templates. As marked by sections, <tt>ncs</tt> (a) makes all possible sub-sequences of the given length, (b) retains those that contain an internal gap, then (c) returns a list of their index-lists.

NB. ======= c ======= ----b---- ========== a ==========

<lang j>NB. ======= c ======= ----b---- ========== a ==========

ncs=: (#&.> <@:i.)~ <"1@: (#~ gap) @:(([ $ 2:) #: i.@(2^]))

gap=: +./@:((1 i.~ 1 0 E. ])<(1 i:~ 0 1 E. ]))"1 1 @: ((##0:),.])

ncs_of=: # (ncs@[ {&.> ]) <

ncs_of=: # (ncs@[ {&.> ]) <</lang>

Examples:

ncs 4

<lang j> ncs 4

+---+---+---+-----+-----+

|1 3|0 3|0 2|0 2 3|0 1 3|

+---+---+---+-----+-----+

ncs_of 9 8 7 6

+---+---+---+-----+-----+

|8 6|9 6|9 7|9 7 6|9 8 6|

+---+---+---+-----+-----+

ncs_of 'aeiou'

+--+--+--+---+---+--+--+---+--+---+---+----+---+---+----+----+

|iu|eu|eo|eou|eiu|au|ao|aou|ai|aiu|aio|aiou|aeu|aeo|aeou|aeiu|

+--+--+--+---+---+--+--+---+--+---+---+----+---+---+----+----+

+--+--+--+---+---+--+--+---+--+---+---+----+---+---+----+----+</lang>

=={{header|JavaScript}}==

Line 350:

<lang Mathematica>GoodBad[i_List]:=Not[MatchQ[Differences[i],{1..}|{}]]

n=5

Select[Subsets[Range[n]],GoodBad]

Select[Subsets[Range[n]],GoodBad]</lang>

</lang>

gives back:

=={{header|OCaml}}==

Line 401:

Line 400:

variables to keep track if subsequence is continuous.

<~~pre~~>define ncsubseq(l);

<lang pop11>define ncsubseq(l);

lvars acc = [], gap_started = false, is_continuous = true;

define do_it(l1, l2);

Line 424:

Line 423:

enddefine;

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

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

Output:

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

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

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

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