Non-continuous subsequences: Difference between revisions

A ''continuous'' subsequence is one in which no elements are missing between the first and last elements of the subsequence.

 

 

 

 

=={{header|Ada}}==

 

procedure Test_Non_Continuous is

Put_NCS ((1,2,3,4)); New_Line;

Put_NCS ((1,2,3,4,5)); New_Line;

 

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

 

2 5

3 5</pre>

 

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?p=277328#277328 discussion]

 

MsgBox % noncontinuous("1,2,3,4", ",")

 

ToBin(n,W=16) { ; LS W-bits of Binary representation of n

Return W=1 ? n&1 : ToBin(n>>1,W-1) . n&1

 

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

looking at the screen wondering what's wrong for about half an hour -->

 

(labels ((subsequences (tail &optional (acc '()) (result '()))

"Return a list of the subsequence designators of the

(map-into subsequence-d 'first subsequence-d)))

(let ((nc-subsequences (delete-if #'continuous-p (subsequences list))))

 

{{trans|Scheme}}

 

(labels ((recurse (s list)

(if (endp list)

(recurse s xs))

(recurse (+ s 1) xs)))))))

 

=={{header|D}}==

if (seq.length) {

aux ~= seq[0] ~ ys;

} else

}

 

 

 

T[] seq;

 

 

bool nc = false;

if (k == 0) {

if (nc) {

result = dg(auxS);

if (result)

}

break;

nc = true;

}

}

 

 

 

 

=={{header|Haskell}}==

===Generalized monadic filter===

 

 

fenceM p q s [] = guard (q s) >> return []

return $ f x ys

 

 

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

[[1,3]]

This implementation works by computing templates of all possible subsequences of the given length of sequence, discarding the continuous ones, then applying the remaining templates to the input list.

 

ncs xs = map (map fst . filter snd . zip xs) $

filter (not . continuous) $

 

===Recursive===

Recursive method with powerset as helper function.

 

 

 

ncsubs [] = [[]]

nc (_:x:xs) [] = nc [x] xs

 

*Main> ncsubs "aaa"

["aa"]

[]

(0.00 secs, 0 bytes)

 

=={{header|J}}==

 

=={{header|JavaScript}}==

 

{{works with|SpiderMonkey}}

var non_continuous = new Array();

for (var i = 0; i < ary.length; i++) {

load('json2.js'); /* http://www.json.org/js.html */

 

 

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

 

 

n=5

 

 

 

=={{header|OCaml}}==

{{trans|Generalized monadic filter}}

 

[] ->

if s >= 3 then

fence (s + 1) xs

 

 

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

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

[1; 3; 5]; [1; 3]; [1; 4; 5]; [1; 4]; [1; 5]; [2; 3; 5]; [2; 4; 5];

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

 

=={{header|Pop11}}==

 

variables to keep track if subsequence is continuous.

 

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

define do_it(l1, l2);

enddefine;

 

 

 

 

=={{header|Python}}==

{{trans|Scheme}}

 

if seq:

x = seq[:1]

return [x + ys for ys in ncsub(xs, s + p1)] + ncsub(xs, s + p2)

else:

 

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

[[1, 3]]

A faster Python + Psyco JIT version:

 

import psyco

 

return result

 

nsubs = lambda n: sum(C(n, k) for k in xrange(3, n+1))

 

psyco.full()

n = 10 if len(argv) < 2 else int(argv[1])

=={{header|R}}==

The idea behind this is to loop over the possible lengths of subsequence, finding all subsequences then discarding those which are continuous.

 

{

n <- length(x)

# Example usage

ncsub(1:4)

 

=={{header|Ruby}}==

Uses code from [[Power Set]].

 

def func_power_set

inject([[]]) { |ps,item| # for each item in the Array

}

end

def non_continuous_subsequences

end

true

end

p (1..3).to_a.non_continuous_subsequences

p (1..4).to_a.non_continuous_subsequences

 

<pre>[[1, 3]]

[[1, 3], [1, 4], [2, 4], [1, 2, 4], [1, 3, 4]]

[[1, 3], [1, 4], [2, 4], [1, 2, 4], [1, 3, 4], [1, 5], [2, 5], [1, 2, 5], [3, 5], [1, 3, 5],

 

 

 

(let recurse ((s 0)

(lst lst))

(map (lambda (ys) (cons x ys))

(recurse s xs))

 

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

((1 3))

> (ncsubseq '(1 2 3 4 5))

((1 2 3 5) (1 2 4 5) (1 2 4) (1 2 5) (1 3 4 5) (1 3 4) (1 3 5) (1 3) (1 4 5) (1 4) (1 5) (2 3 5) (2 4 5) (2 4) (2 5) (3 5))</pre>

 

=={{header|Standard ML}}==

{{trans|Generalized monadic filter}}

 

if s >= 3 then

[[]]

fence (s + 1) xs

 

 

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

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

This Tcl implementation uses the ''subsets'' function from [[Power Set]], which is acceptable as that conserves the ordering, as well as a problem-specific test function ''is_not_continuous'' and a generic list filter ''lfilter'':

 

set res [list [list]]

foreach e $l {

 

% lfilter is_not_continuous [subsets {1 2 3 4}]

 

=={{header|Ursala}}==

To do it the lazy programmer way, apply the powerset library function to the list, which will generate all continuous and non-continuous subsequences of it, and then delete the subsequences that are also substrings (hence continuous) using a judicious combination of the built in substring predicate (K3), negation (Z), and distributing filter (K17) operator suffixes. This function will work on lists of any type. To meet the requirement for structural equivalence, the list items are first uniquely numbered (num), and the numbers are removed afterwards (rSS).

 

 

noncontinuous = num; ^rlK3ZK17rSS/~& powerset

#show+

 

 

<pre>abce

abd

be

ce</pre>