Non-continuous subsequences: Difference between revisions

Line 13:

=={{header|Ada}}==

<lang ada>with Ada.Text_IO; use Ada.Text_IO;

with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Non_Continuous is

Line 50:

Line 49:

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

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

end Test_Non_Continuous;

end Test_Non_Continuous;</lang>

</lang>

Sample output:

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

1 3

1 2 4

Line 77:

Line 76:

2 4 5

2 5

3 5

3 5</pre>

</pre>

=={{header|AutoHotkey}}==

using filtered templates

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

<lang AutoHotkey>MsgBox % noncontinuous("a,b,c,d,e", ",")

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

Line 101:

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

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

}</lang>

}

</lang>

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

Line 132:

Line 131:

(map-into nc-subsequences #'designated-sequence nc-subsequences))))</lang>

~~From~~ Scheme ~~version:~~

<lang lisp>(defun all-subsequences2 (list)

Line 155:

Line 154:

A short version adapted from the Python code:

<lang d>import std.stdio: writefln;

import std.stdio: writefln;

T[][] ncsub(T)(T[] seq, int s=0) {

Line 172:

Line 170:

writefln(ncsub([1, 2, 3, 4]));

writefln(ncsub([1, 2, 3, 4, 5]));

}</lang>

}

</lang>

Output:

<pre>

[[1,3]]

<pre>[[1,3]]

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

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

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

</pre>

A fast lazy version, it doesn't copy the generated sub-arrays, so if you want to keep them you have to copy (dup) them:

A fast lazy version. It doesn't copy the generated sub-arrays, so if you want to keep them you have to copy (dup) them:

<lang d>import std.conv: toInt;

import std.conv: toInt;

import std.stdio: writefln;

Line 232:

Line 227:

count++;

writefln(count);

}</lang>

}

</lang>

=={{header|Haskell}}==

Line 239:

Line 233:

===Generalized monadic filter===

<lang haskell>action p x = if p x then succ x else x

<pre>

action p x = if p x then succ x else x

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

Line 248:

Line 241:

return $ f x ys

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

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

</pre>

Output:

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

<pre>

*Main> ncsubseq [1..3]

[[1,3]]

*Main> ncsubseq [1..4]

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

*Main> ncsubseq [1..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]]

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

</pre>

===Filtered templates===

Line 266:

Line 256:

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.

continuous = null . dropWhile not . dropWhile id . dropWhile not

<lang haskell>continuous = null . dropWhile not . dropWhile id . dropWhile not

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

filter (not . continuous) $

mapM (const [True,False]) xs

mapM (const [True,False]) xs</lang>

===Recursive===

Recursive method with powerset as helper function.

import Data.List

poset [] = [[]]

poset (x:xs) = let p = poset xs in p ++ map (x:) p

ncsubs [] = [[]]

ncsubs (x:xs) =

let

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

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

nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)

in tail $ nc [x] xs

<lang haskell>import Data.List

:Output

poset [] = [[]]

poset (x:xs) = let p = poset xs in p ++ map (x:) p

ncsubs [] = [[]]

ncsubs (x:xs) =

let

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

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

nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)

in tail $ nc [x] xs</lang>

Output:

*Main> ncsubs "aaa"

["aa"]

Line 322:

Line 315:

=={{header|Mathematica}}==

We make all the subsets then filter out the continuous ones:

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

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

n=5

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

</lang>

gives back:

{{1,3},{1,4},{1,5},{2,4},{2,5},{3,5},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,5},{2,4,5},{1,2,3,5},{1,2,4,5},{1,3,4,5}}

</lang>

=={{header|OCaml}}==

~~Taken from the Haskell's~~ monadic filter ~~example.~~

<lang ocaml>let rec fence s = function

let rec fence s = function

[] ->

if s >= 3 then

Line 358:

Line 350:

fence (s + 1) xs

let ncsubseq = fence 0

let ncsubseq = fence 0</lang>

</lang>

Output:

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

<pre>

# ncsubseq [1;2;3];;

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

# ncsubseq [1;2;3;4];;

Line 372:

Line 362:

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

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

</pre>

=={{header|Pop11}}==

Line 380:

Line 369:

variables to keep track if subsequence is continuous.

<pre>

<pre>define ncsubseq(l);

define ncsubseq(l);

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

define do_it(l1, l2);

Line 404:

Line 392:

enddefine;

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

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

</pre>

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]

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

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

</pre>

=={{header|Python}}==

Adapted from the Scheme version.

<lang python>def ncsub(seq, s=0):

<pre>

def ncsub(seq, s=0):

if seq:

x = seq[:1]

Line 426:

Line 410:

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

else:

return [[]] if s >= 3 else []

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

</pre>

Output:

<pre>

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

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

[[1, 3]]

>>> ncsub(range(1, 5))

Line 438:

Line 421:

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

[2, 5], [3, 5]]</pre>

</pre>

A faster Python + Psyco JIT version:

<lang python>from sys import argv

<pre>

from sys import argv

import psyco

Line 483:

Line 464:

psyco.full()

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

print len( ncsub(range(1, n)) )

print len( ncsub(range(1, n)) )</lang>

</pre>

=={{header|R}}==

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

ncsub <- function(x)

<lang r>ncsub <- function(x)

{

n <- length(x)

Line 505:

Line 485:

# Example usage

ncsub(1:4)

ncsub(letters[1:5])

ncsub(letters[1:5])</lang>

</lang>

=={{header|Ruby}}==

Uses code from [[Power Set]]

Uses code from [[Power Set]].

<lang ruby>class Array

def func_power_set

Line 533:

Line 513:

p (1..4).to_a.non_continuous_subsequences

p (1..5).to_a.non_continuous_subsequences</lang>

<pre>[[1, 3]]

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

Line 540:

Line 521:

=={{header|Scheme}}==

~~Taken from the Haskell's~~ monadic filter ~~example.~~

<lang scheme>(define (ncsubseq lst)

(define (ncsubseq lst)

(let recurse ((s 0)

(lst lst))

Line 560:

Line 540:

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

(recurse s xs))

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

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

</lang>

Output:

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

<pre>

> (ncsubseq '(1 2 3))

((1 3))

> (ncsubseq '(1 2 3 4))

((1 2 4) (1 3 4) (1 3) (1 4) (2 4))

> (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))

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

</pre>

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

~~Taken from the Haskell's~~ monadic filter ~~example.~~

<lang sml>fun fence s [] =

fun fence s [] =

if s >= 3 then

[[]]

Line 599:

Line 575:

fence (s + 1) xs

fun ncsubseq xs = fence 0 xs

fun ncsubseq xs = fence 0 xs</lang>

</lang>

Output:

<pre>

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

- ncsubseq [1,2,3];

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

- ncsubseq [1,2,3,4];

Line 612:

Line 586:

val it =

[[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],...] : int list list

[1,4,5],[1,4],[1,5],[2,3,5],...] : int list list</pre>

</pre>

=={{header|Tcl}}==

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

<lang Tcl> proc subsets l {

proc subsets l {

set res [list [list]]

foreach e $l {

Line 641:

Line 613:

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

{1 3} {1 4} {2 4} {1 2 4} {1 3 4}

{1 3} {1 4} {2 4} {1 2 4} {1 3 4}</lang>

</lang>

=={{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).

To do it the lazy programmer way, apply the powerset library function to the

list, which will generate all continuous and non-continuous subsequences

<lang Ursala>#import std

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

#import std

noncontinuous = num; ^rlK3ZK17rSS/~& powerset

Line 663:

Line 626:

examples = noncontinuous 'abcde'</lang>

output:

Output:

<pre>abce

abd