Jump to content

Non-continuous subsequences: Difference between revisions

Non-continuous subsequences (view source)

Revision as of 13:58, 6 November 2009

32 bytes removed ,  14 years ago
Miscellaneous formatting changes.
(Added R code)
(Miscellaneous formatting changes.)
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 ⟶ 49:
Put_NCS ((1,2,3,4)); New_Line;
Put_NCS ((1,2,3,4,5)); New_Line;
end Test_Non_Continuous;</lang>
 
</lang>
Sample output:
 
<pre style="height:30ex;overflow:scroll">
<pre style="height:30ex;overflow:scroll"> 1 3
1 3
 
1 2 4
Line 77 ⟶ 76:
2 4 5
2 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 ⟶ 131:
(map-into nc-subsequences #'designated-sequence nc-subsequences))))</lang>
 
From {{trans|Scheme version:}}
 
<lang lisp>(defun all-subsequences2 (list)
Line 155 ⟶ 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 ⟶ 170:
writefln(ncsub([1, 2, 3, 4]));
writefln(ncsub([1, 2, 3, 4, 5]));
}</lang>
}
</lang>
 
Output:
 
<pre>
<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]]</pre>
</pre>
 
A fast lazy version,. itIt 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 ⟶ 227:
count++;
writefln(count);
}</lang>
}
</lang>
 
=={{header|Haskell}}==
Line 239 ⟶ 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 ⟶ 241:
return $ f x ys
 
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]]</pre>
</pre>
 
===Filtered templates===
Line 266 ⟶ 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.
 
<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</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 ⟶ 315:
=={{header|Mathematica}}==
We make all the subsets then filter out the continuous ones:
 
<lang Mathematica>
<lang Mathematica>GoodBad[i_List]:=Not[MatchQ[Differences[i],{1..}|{}]]
n=5
Select[Subsets[Range[n]],GoodBad]
</lang>
 
gives back:
 
<lang Mathematica>
<lang Mathematica> {{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>
</lang>
 
=={{header|OCaml}}==
 
Taken from the Haskell's{{trans|Generalized monadic filter example.}}
 
<lang ocaml>let rec fence s = function
let rec fence s = function
[] ->
if s >= 3 then
Line 358 ⟶ 350:
fence (s + 1) xs
 
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 ⟶ 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]]</pre>
</pre>
 
=={{header|Pop11}}==
Line 380 ⟶ 369:
variables to keep track if subsequence is continuous.
 
<pre>define ncsubseq(l);
define ncsubseq(l);
lvars acc = [], gap_started = false, is_continuous = true;
define do_it(l1, l2);
Line 404 ⟶ 392:
enddefine;
 
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 43 5] [1 2 43 5] [1 3 4] [1 5] [2 4 5] [1 2 5] [34 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}}==
{{trans|Scheme}}
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 ⟶ 410:
return [x + ys for ys in ncsub(xs, s + p1)] + ncsub(xs, s + p2)
else:
return [[]] if s >= 3 else []</lang>
</pre>
 
Output:
 
<pre>
<pre>>>> ncsub(range(1, 4))
[[1, 3]]
>>> ncsub(range(1, 5))
Line 438 ⟶ 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]]</pre>
</pre>
 
A faster Python + Psyco JIT version:
 
<lang python>from sys import argv
<pre>
from sys import argv
import psyco
 
Line 483 ⟶ 464:
psyco.full()
n = 10 if len(argv) < 2 else int(argv[1])
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.
 
<lang r>
<lang r>ncsub <- function(x)
{
n <- length(x)
Line 505 ⟶ 485:
# Example usage
ncsub(1:4)
ncsub(letters[1:5])</lang>
</lang>
 
=={{header|Ruby}}==
{{trans|Tcl}}
 
Uses code from [[Power Set]].
 
<lang ruby>class Array
def func_power_set
Line 533 ⟶ 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 ⟶ 521:
=={{header|Scheme}}==
 
Taken from the Haskell's{{trans|Generalized monadic filter example.}}
 
<lang scheme>(define (ncsubseq lst)
(define (ncsubseq lst)
(let recurse ((s 0)
(lst lst))
Line 560 ⟶ 540:
(map (lambda (ys) (cons x ys))
(recurse s 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))</pre>
</pre>
 
=={{header|Standard ML}}==
 
Taken from the Haskell's{{trans|Generalized monadic filter example.}}
 
<lang sml>fun fence s [] =
fun fence s [] =
if s >= 3 then
[[]]
Line 599 ⟶ 575:
fence (s + 1) xs
 
fun ncsubseq xs = fence 0 xs</lang>
</lang>
 
Output:
 
<pre>- ncsubseq [1,2,3];
- ncsubseq [1,2,3];
val it = [[1,3]] : int list list
- ncsubseq [1,2,3,4];
Line 612 ⟶ 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</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 ⟶ 613:
 
% lfilter is_not_continuous [subsets {1 2 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).
<lang Ursala>
#import std
 
noncontinuous = num; ^rlK3ZK17rSS/~& powerset
Line 663 ⟶ 626:
 
examples = noncontinuous 'abcde'</lang>
 
output:
Output:
 
<pre>abce
abd
Underscore
845

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/65301"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information