Non-continuous subsequences: Difference between revisions

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.

 

 

 

=={{header|Ada}}==

===Recursive===

 

procedure Test_Non_Continuous is

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

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

 

{{out}}

2 5

3 5</pre>

=={{header|ALGOL 68}}==

===Recursive===

 

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

MODE SEQMODE = CHAR;

MODE SEQ = [1:0]SEQMODE;

print((seq, new line))

# OD # )

{{out}}

<pre>

 

Note: This specimen can only handle sequences of length less than ''bits width'' of '''bits'''.

MODE SEQ = [1:0]SEQMODE;

MODE YIELDSEQ = PROC(SEQ)VOID;

print((seq, new line))

# OD # )

{{out}}

<pre>

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|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

list1$() = "1", "2", "3", "4"

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

NEXT g%

NEXT s%

{{out}}

<pre>

 

=={{header|Bracmat}}==

= sub

. ( sub

& noncontinuous$(e r n i t)

);

{{out}}

<pre>e n t

=={{header|C}}==

Note: This specimen can only handle lists of length less than the number of bits in an '''int'''.

#include <stdio.h>

 

 

return 0;

Example use:

<pre>

 

Using "consecutive + gap + any subsequence" to produce disjointed sequences:

#include <stdio.h>

#include <stdlib.h>

 

return 0;

===Recursive method===

Using recursion and a state transition table.

 

typedef unsigned char sint;

pick(c - 1, 0, s_blnk, v + 1, 0);

return 0;

<pre>% ./a.out 1 2 3 4

1 3

968</pre>

 

 

 

 

{{out}}

 

=={{header|Clojure}}==

Here's a simple approach that uses the clojure.contrib.combinatorics library to generate subsequences, and then filters out the continuous subsequences using a naïve subseq test:

 

(use '[clojure.contrib.combinatorics :only (subsets)])

 

 

(filter (of-min-length 2) (non-continuous-subsequences [:a :b :c :d]))

 

=={{header|CoffeeScript}}==

Use binary bitmasks to enumerate our sequences.

is_contigous_binary = (n) ->

# return true if binary representation of n is

num_solutions = non_contig_subsequences(arr).length

console.log "for n=#{n} there are #{num_solutions} solutions"

 

{{out}}

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}}==

===Recursive Version===

{{trans|Python}}

if (seq.length) {

typeof(return) aux;

foreach (const nc; [1, 2, 3, 4, 5].ncsub)

nc.writeln;

{{out}}

<pre>[[1, 3]]

===Faster Lazy Version===

This version doesn't copy the sub-arrays.

T[] seq;

 

counter++;

assert(counter == 16_776_915);

 

===Generator Version===

This version doesn't copy the sub-arrays, and it's a little slower than the opApply-based version.

 

Generator!(T[]) ncsub(T)(in T[] seq) {

foreach (const nc; [1, 2, 3, 4, 5].ncsub)

nc.writeln;

 

=={{header|Erlang}}==

Erlang's not optimized for strings or math, so this is pretty inefficient. Nonetheless, it works by generating the set of all possible "bitmasks" (represented as strings), filters for those with non-continuous subsequences, and maps from that set over the list. One immediate point for optimization that would complicate the code a bit would be to compile the regular expression, the problem being where you'd put it.

 

-export([ncs/1]).

 

ncs(List) ->

lists:map(fun(Mask) -> apply_mask_to_list(Mask, List) end,

 

{{out}}

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

</pre>

 

=={{header|Go}}==

Generate the power set (power sequence, actually) with a recursive function, but keep track of the state of the subsequence on the way down. When you get to the bottom, if state == non-continuous, then include the subsequence. It's just filtering merged in with generation.

 

import "fmt"

fmt.Println(" ", s)

}

{{out}}

<pre>

===Generalized monadic filter===

 

 

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

return $ f x ys

 

 

{{out}}

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.

 

 

poset = foldr (\x p -> p ++ map (x:) p) [[]]

nc [_] [] = [[]]

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

 

{{out}}

A disjointed subsequence is a consecutive subsequence followed by a gap,

then by any nonempty subsequence to its right:

 

disjoint a = concatMap (cutAt a) [1..length a - 2] where

(left, _:right) = splitAt n s

 

 

Build a lexicographic list of consecutive subsequences,

and a list of all subsequences, then subtract one from the other:

 

subseqs = foldr (\x s -> [x] : map (x:) s ++ s) []

disjoint s = (subseqs s) `minus` (consecs s)

 

 

=={{header|J}}==

We select those combinations where the end of the first continuous subsequence appears before the start of the last continuous subsequence:

 

firstend=:1 0 i.&1@E."1 ]

laststart=: 0 1 {:@I.@E."1 ]

 

Example use:

┌───┬───┬───┬─────┬─────┐

│2 4│1 4│1 3│1 3 4│1 2 4│

└──┴──┴──┴───┴───┴──┴──┴───┴──┴───┴───┴────┴───┴───┴────┴────┘

#noncont i.10

 

Alternatively, since there are relatively few continuous sequences, we could specifically exclude them:

 

 

(we get the same behavior from this implementation)

 

=={{header|Java}}==

 

public static void main(String args[]) {

}

}

 

<pre>12 4

 

{{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 */

 

 

{{out}}

subsets, we will use the powerset approach, and accordingly begin by

defining subsets/0 as a generator.

def subsets:

if length == 0 then []

def non_continuous_subsequences:

(length | non_continuous_indices) as $ix

'''Example''':

To show that the above approach can be used for relatively large n, let us count the number of non-continuous subsequences of [0, 1, ..., 19].

 

count( [range(0;20)] | non_continuous_subsequences)

{{out}}

$ jq -n -f powerset_generator.jq

 

'''Iterator and Functions'''

 

function makeint2seq(n::Integer)

function int2seq(m::Integer)

idex[d .== 1]

end

return int2seq

end

n::T

end

m::T

m2s::Function

end

s = as.m2s(as.m)

as.m += 1

return (s, as)

end

n = 4

s = "Rosetta"

cs = split(s, "")

m = 10

i <= m || n < i || continue

println(@sprintf "%6d %s" i join(cs[a], ""))

end

 

end

<pre>

Testing NCSubSeq for 4 items:

 

The first and last 10 NC sub-sequences of "Rosetta":

99 Rsetta

 

</pre>

 

 

 

 

 

=={{header|Nim}}==

{{trans|Python}}

 

proc ncsub[T](se: seq[T], s = 0): seq[seq[T]] =

let

x = se[0..0]

p2 = s mod 2

p1 = (s + 1) mod 2

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

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

{{out}}

<pre>ncsub(@[1, 2, 3]) = @[@[1, 3]]

{{trans|Generalized monadic filter}}

 

[] ->

if s >= 3 then

fence (s + 1) xs

 

 

{{out}}

=={{header|Oz}}==

A nice application of finite set constraints. We just describe what we want and the constraint system will deliver it:

fun {NCSubseq SeqList}

Seq = {FS.value.make SeqList}

end

in

 

=={{header|PARI/GP}}==

Just a simple script, but it's I/O bound so efficiency isn't a concern. (Almost all subsequences are non-contiguous so looping over all possibilities isn't that bad. For length 20 about 99.98% of subsequences are non-contiguous.)

nonContigSubseq(v)={

for(i=5,2^#v-1,

};

nonContigSubseq([1,2,3])

{{out}}

<pre>[1, 3]

 

=={{header|Perl}}==

sub non_continuous {

 

for ($idx .. $max) {

}

 

 

 

{{out}}

 

=={{header|PicoLisp}}==

{{trans|Scheme}}

(let S 0

(recur (S Lst)

(mapcar '((YS) (cons X YS))

(recurse S XS) )

 

=={{header|Pop11}}==

variables to keep track if subsequence is continuous.

 

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

define do_it(l1, l2);

enddefine;

 

 

{{out}}

 

=={{header|PowerShell}}==

{

$sc = $S.count

}

 

 

=={{header|Prolog}}==

We explain to Prolog how to build a non continuous subsequence of a list L, then we ask Prolog to fetch all the subsequences.

 

% fetch all the subsequences

ncsubs(L, LNCSL) :-

reverse(L, [_|SL1]),

reverse(SL1, SL)).

Example :

 

=={{header|Python}}==

{{trans|Scheme}}

 

if seq:

x = seq[:1]

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

else:

 

{{out}}

A faster Python + Psyco JIT version:

 

import psyco

 

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|Racket}}==

 

Take a simple <tt>subsets</tt> definition:

(define (subsets l)

(if (null? l) '(())

(append (for/list ([l2 (subsets (cdr l))]) (cons (car l) l2))

(subsets (cdr l)))))

since the subsets are returned in their original order, it is also a sub-sequences function.

 

Now add to it a "state" counter which count one for each chunk of items included or excluded. It's always even when we're in an excluded chunk (including the beginning) and odd when we're including items -- increment it whenever we switch from one kind of chunk to the other. This means that we should only include subsequences where the state is 3 (included->excluded->included) or more. Note that this results in code that is similar to the "Generalized monadic filter" entry, except a little simpler.

 

#lang racket

(define (non-continuous-subseqs l)

(non-continuous-subseqs '(1 2 3 4))

;; => '((1 2 4) (1 3 4) (1 3) (1 4) (2 4))

 

 

 

 

<pre>

list= 1 2 3 4

5 non-continuous subsequences were found.

</pre>

<pre>

list= a e I o u

16 non-continuous subsequences were found.

</pre>

<pre>

list= Alderney Guernsey Herm Jersey Sark

16 non-continuous subsequences were found.

</pre>

<pre>

list= helium neon argon krypton xenon radon

 

42 non-continuous subsequences were found.

</pre>

 

Uses code from [[Power Set]].

 

def func_power_set

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

p (1..4).to_a.non_continuous_subsequences

p (1..5).to_a.non_continuous_subsequences

 

{{out}}

</pre>

It is not the value of the array element and when judging continuation in the position, it changes as follows.

def continuous?(seq)

seq.each_cons(2) {|a, b| return false if index(a)+1 != index(b)}

end

 

 

{{out}}

<pre>[["a", "i"], ["a", "o"], ["e", "o"], ["a", "e", "o"], ["a", "i", "o"], ["a", "u"], ["e", "u"], ["a", "e", "u"], ["i", "u"], ["a", "i", "u"], ["e", "i", "u"], ["a", "e", "i", "u"], ["a", "o", "u"], ["e", "o", "u"], ["a", "e", "o", "u"], ["a", "i", "o", "u"]]</pre>

 

 

 

(let recurse ((s 0)

(lst lst))

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

(recurse s xs))

 

{{out}}

 

=={{header|Seed7}}==

 

const func array bitset: ncsub (in bitset: seq, in integer: s) is func

writeln(seq);

end for;

 

{{out}}

=={{header|Sidef}}==

{{trans|Perl}}

 

static current = [];

 

i < max && non_continuous(i.inc, max, subseq, has_gap);

current.pop;

}

 

say non_continuous(1, 3);

say non_continuous(1, 4);

{{out}}

<pre>

{{trans|Generalized monadic filter}}

 

if s >= 3 then

[[]]

fence (s + 1) xs

 

 

{{out}}

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+

 

 

{{out}}

be

ce</pre>

 

=={{header|zkl}}==

{{trans|JavaScript}}

pwerSet(ary).filter(fcn(list){(not isContinuous(list)) })

}

return(True);

}

(0).pump(list.len(),List,List,Utils.Helpers.pickNFrom.fp1(list),

T(T,Void.Write,Void.Write) ) .append(list)

pwerSet(str.split("")).apply("concat")

.filter('wrap(substr){ (not str.holds(substr)) })

}

{{out}}

<pre>