Non-continuous subsequences: Difference between revisions
Content added Content deleted
m (→{{header|Picat}}: code tag for predicates) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 33: | Line 33: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F ncsub(seq, s = 0) |
||
I seq.empty |
I seq.empty |
||
R I s >= 3 {[[Int]()]} E [[Int]]() |
R I s >= 3 {[[Int]()]} E [[Int]]() |
||
Line 45: | Line 45: | ||
print(ncsub(Array(1..3))) |
print(ncsub(Array(1..3))) |
||
print(ncsub(Array(1..4))) |
print(ncsub(Array(1..4))) |
||
print(ncsub(Array(1..5)))</ |
print(ncsub(Array(1..5)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 56: | Line 56: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
===Recursive=== |
===Recursive=== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
||
procedure Test_Non_Continuous is |
procedure Test_Non_Continuous is |
||
Line 92: | Line 92: | ||
Put_NCS ((1,2,3,4)); New_Line; |
Put_NCS ((1,2,3,4)); New_Line; |
||
Put_NCS ((1,2,3,4,5)); New_Line; |
Put_NCS ((1,2,3,4,5)); New_Line; |
||
end Test_Non_Continuous;</ |
end Test_Non_Continuous;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 127: | Line 127: | ||
{{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]}} |
{{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]}} |
||
< |
<syntaxhighlight lang="algol68">PROC test non continuous = VOID: BEGIN |
||
MODE SEQMODE = CHAR; |
MODE SEQMODE = CHAR; |
||
MODE SEQ = [1:0]SEQMODE; |
MODE SEQ = [1:0]SEQMODE; |
||
Line 161: | Line 161: | ||
print((seq, new line)) |
print((seq, new line)) |
||
# OD # ) |
# OD # ) |
||
END; test non continuous</ |
END; test non continuous</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 191: | Line 191: | ||
Note: This specimen can only handle sequences of length less than ''bits width'' of '''bits'''. |
Note: This specimen can only handle sequences of length less than ''bits width'' of '''bits'''. |
||
< |
<syntaxhighlight lang="algol68">MODE SEQMODE = STRING; |
||
MODE SEQ = [1:0]SEQMODE; |
MODE SEQ = [1:0]SEQMODE; |
||
MODE YIELDSEQ = PROC(SEQ)VOID; |
MODE YIELDSEQ = PROC(SEQ)VOID; |
||
Line 237: | Line 237: | ||
print((seq, new line)) |
print((seq, new line)) |
||
# OD # ) |
# OD # ) |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 262: | Line 262: | ||
ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?p=277328#277328 discussion] |
ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?p=277328#277328 discussion] |
||
< |
<syntaxhighlight lang="autohotkey">MsgBox % noncontinuous("a,b,c,d,e", ",") |
||
MsgBox % noncontinuous("1,2,3,4", ",") |
MsgBox % noncontinuous("1,2,3,4", ",") |
||
Line 281: | Line 281: | ||
ToBin(n,W=16) { ; LS W-bits of Binary representation of n |
ToBin(n,W=16) { ; LS W-bits of Binary representation of n |
||
Return W=1 ? n&1 : ToBin(n>>1,W-1) . n&1 |
Return W=1 ? n&1 : ToBin(n>>1,W-1) . n&1 |
||
}</ |
}</syntaxhighlight> |
||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM list1$(3) |
||
list1$() = "1", "2", "3", "4" |
list1$() = "1", "2", "3", "4" |
||
PRINT "For [1, 2, 3, 4] non-continuous subsequences are:" |
PRINT "For [1, 2, 3, 4] non-continuous subsequences are:" |
||
Line 316: | Line 316: | ||
NEXT g% |
NEXT g% |
||
NEXT s% |
NEXT s% |
||
ENDPROC</ |
ENDPROC</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 345: | Line 345: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang="bracmat">( ( noncontinuous |
||
= sub |
= sub |
||
. ( sub |
. ( sub |
||
Line 365: | Line 365: | ||
& noncontinuous$(e r n i t) |
& noncontinuous$(e r n i t) |
||
); |
); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>e n t |
<pre>e n t |
||
Line 386: | Line 386: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Note: This specimen can only handle lists of length less than the number of bits in an '''int'''. |
Note: This specimen can only handle lists of length less than the number of bits in an '''int'''. |
||
< |
<syntaxhighlight lang="c">#include <assert.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 405: | Line 405: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
Example use: |
Example use: |
||
<pre> |
<pre> |
||
Line 419: | Line 419: | ||
Using "consecutive + gap + any subsequence" to produce disjointed sequences: |
Using "consecutive + gap + any subsequence" to produce disjointed sequences: |
||
< |
<syntaxhighlight lang="c">#include <assert.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 443: | Line 443: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
===Recursive method=== |
===Recursive method=== |
||
Using recursion and a state transition table. |
Using recursion and a state transition table. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
typedef unsigned char sint; |
typedef unsigned char sint; |
||
Line 496: | Line 496: | ||
pick(c - 1, 0, s_blnk, v + 1, 0); |
pick(c - 1, 0, s_blnk, v + 1, 0); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight>running it: |
||
<pre>% ./a.out 1 2 3 4 |
<pre>% ./a.out 1 2 3 4 |
||
1 3 |
1 3 |
||
Line 507: | Line 507: | ||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 536: | Line 536: | ||
static bool IsContinuous(List<int> list) => list[list.Count - 1] - list[0] + 1 == list.Count; |
static bool IsContinuous(List<int> list) => list[list.Count - 1] - list[0] + 1 == list.Count; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 547: | Line 547: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
/* |
/* |
||
* Nigel Galloway, July 19th., 2017 - Yes well is this any better? |
* Nigel Galloway, July 19th., 2017 - Yes well is this any better? |
||
Line 563: | Line 563: | ||
uint next() {return g;} |
uint next() {return g;} |
||
}; |
}; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Which may be used as follows: |
Which may be used as follows: |
||
< |
<syntaxhighlight lang="cpp"> |
||
int main(){ |
int main(){ |
||
N n(4); |
N n(4); |
||
while (n.hasNext()) std::cout << n.next() << "\t* " << std::bitset<4>(n.next()) << std::endl; |
while (n.hasNext()) std::cout << n.next() << "\t* " << std::bitset<4>(n.next()) << std::endl; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 580: | Line 580: | ||
</pre> |
</pre> |
||
I can count the length of the sequence: |
I can count the length of the sequence: |
||
< |
<syntaxhighlight lang="cpp"> |
||
int main(){ |
int main(){ |
||
N n(31); |
N n(31); |
||
int z{};for (;n.hasNext();++z); std::cout << z << std::endl; |
int z{};for (;n.hasNext();++z); std::cout << z << std::endl; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 595: | Line 595: | ||
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: |
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: |
||
< |
<syntaxhighlight lang="lisp"> |
||
(use '[clojure.contrib.combinatorics :only (subsets)]) |
(use '[clojure.contrib.combinatorics :only (subsets)]) |
||
Line 612: | Line 612: | ||
(filter (of-min-length 2) (non-continuous-subsequences [:a :b :c :d])) |
(filter (of-min-length 2) (non-continuous-subsequences [:a :b :c :d])) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
Use binary bitmasks to enumerate our sequences. |
Use binary bitmasks to enumerate our sequences. |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
is_contigous_binary = (n) -> |
is_contigous_binary = (n) -> |
||
# return true if binary representation of n is |
# return true if binary representation of n is |
||
Line 674: | Line 674: | ||
num_solutions = non_contig_subsequences(arr).length |
num_solutions = non_contig_subsequences(arr).length |
||
console.log "for n=#{n} there are #{num_solutions} solutions" |
console.log "for n=#{n} there are #{num_solutions} solutions" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 702: | Line 702: | ||
looking at the screen wondering what's wrong for about half an hour --> |
looking at the screen wondering what's wrong for about half an hour --> |
||
< |
<syntaxhighlight lang="lisp">(defun all-subsequences (list) |
||
(labels ((subsequences (tail &optional (acc '()) (result '())) |
(labels ((subsequences (tail &optional (acc '()) (result '())) |
||
"Return a list of the subsequence designators of the |
"Return a list of the subsequence designators of the |
||
Line 722: | Line 722: | ||
(map-into subsequence-d 'first subsequence-d))) |
(map-into subsequence-d 'first subsequence-d))) |
||
(let ((nc-subsequences (delete-if #'continuous-p (subsequences list)))) |
(let ((nc-subsequences (delete-if #'continuous-p (subsequences list)))) |
||
(map-into nc-subsequences #'designated-sequence nc-subsequences))))</ |
(map-into nc-subsequences #'designated-sequence nc-subsequences))))</syntaxhighlight> |
||
{{trans|Scheme}} |
{{trans|Scheme}} |
||
< |
<syntaxhighlight lang="lisp">(defun all-subsequences2 (list) |
||
(labels ((recurse (s list) |
(labels ((recurse (s list) |
||
(if (endp list) |
(if (endp list) |
||
Line 741: | Line 741: | ||
(recurse s xs)) |
(recurse s xs)) |
||
(recurse (+ s 1) xs))))))) |
(recurse (+ s 1) xs))))))) |
||
(recurse 0 list)))</ |
(recurse 0 list)))</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
===Recursive Version=== |
===Recursive Version=== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="d">T[][] ncsub(T)(in T[] seq, in uint s=0) pure nothrow @safe { |
||
if (seq.length) { |
if (seq.length) { |
||
typeof(return) aux; |
typeof(return) aux; |
||
Line 763: | Line 763: | ||
foreach (const nc; [1, 2, 3, 4, 5].ncsub) |
foreach (const nc; [1, 2, 3, 4, 5].ncsub) |
||
nc.writeln; |
nc.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[[1, 3]] |
<pre>[[1, 3]] |
||
Line 786: | Line 786: | ||
===Faster Lazy Version=== |
===Faster Lazy Version=== |
||
This version doesn't copy the sub-arrays. |
This version doesn't copy the sub-arrays. |
||
< |
<syntaxhighlight lang="d">struct Ncsub(T) { |
||
T[] seq; |
T[] seq; |
||
Line 828: | Line 828: | ||
counter++; |
counter++; |
||
assert(counter == 16_776_915); |
assert(counter == 16_776_915); |
||
}</ |
}</syntaxhighlight> |
||
===Generator Version=== |
===Generator Version=== |
||
This version doesn't copy the sub-arrays, and it's a little slower than the opApply-based version. |
This version doesn't copy the sub-arrays, and it's a little slower than the opApply-based version. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.array, std.range, std.concurrency; |
||
Generator!(T[]) ncsub(T)(in T[] seq) { |
Generator!(T[]) ncsub(T)(in T[] seq) { |
||
Line 865: | Line 865: | ||
foreach (const nc; [1, 2, 3, 4, 5].ncsub) |
foreach (const nc; [1, 2, 3, 4, 5].ncsub) |
||
nc.writeln; |
nc.writeln; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
defp masks(n) do |
defp masks(n) do |
||
maxmask = trunc(:math.pow(2, n)) - 1 |
maxmask = trunc(:math.pow(2, n)) - 1 |
||
Line 892: | Line 892: | ||
IO.inspect RC.ncs([1,2,3]) |
IO.inspect RC.ncs([1,2,3]) |
||
IO.inspect RC.ncs([1,2,3,4]) |
IO.inspect RC.ncs([1,2,3,4]) |
||
IO.inspect RC.ncs('abcd')</ |
IO.inspect RC.ncs('abcd')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 904: | Line 904: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="erlang">-module(rosetta). |
||
-export([ncs/1]). |
-export([ncs/1]). |
||
Line 927: | Line 927: | ||
ncs(List) -> |
ncs(List) -> |
||
lists:map(fun(Mask) -> apply_mask_to_list(Mask, List) end, |
lists:map(fun(Mask) -> apply_mask_to_list(Mask, List) end, |
||
masks(length(List))).</ |
masks(length(List))).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 940: | Line 940: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===Generate only the non-continuous subsequences=== |
===Generate only the non-continuous subsequences=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
(* |
(* |
||
A function to generate only the non-continuous subsequences. |
A function to generate only the non-continuous subsequences. |
||
Line 949: | Line 949: | ||
let rec fg n = seq{if n>0 then yield! seq{1..((1<<<n)-1)}|>fn n; yield! fg (n-1)|>fn n} |
let rec fg n = seq{if n>0 then yield! seq{1..((1<<<n)-1)}|>fn n; yield! fg (n-1)|>fn n} |
||
Seq.collect fg ({1..(n-2)}) |
Seq.collect fg ({1..(n-2)}) |
||
</syntaxhighlight> |
|||
</lang> |
|||
This may be used as follows: |
This may be used as follows: |
||
< |
<syntaxhighlight lang="fsharp"> |
||
let Ng ng = N ng |> Seq.iter(fun n->printf "%2d -> " n; {0..(ng-1)}|>Seq.iter (fun g->if (n&&&(1<<<g))>0 then printf "%d " (g+1));printfn "") |
let Ng ng = N ng |> Seq.iter(fun n->printf "%2d -> " n; {0..(ng-1)}|>Seq.iter (fun g->if (n&&&(1<<<g))>0 then printf "%d " (g+1));printfn "") |
||
Ng 4 |
Ng 4 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 979: | Line 979: | ||
</pre> |
</pre> |
||
===Generate all subsequences and filter out the continuous=== |
===Generate all subsequences and filter out the continuous=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
(* |
(* |
||
A function to filter out continuous subsequences. |
A function to filter out continuous subsequences. |
||
Line 990: | Line 990: | ||
|(n,_) ->n |
|(n,_) ->n |
||
{5..(1<<<n)-1}|>Seq.choose(fun i->if fst({0..n-1}|>Seq.takeWhile(fun n->(1<<<(n-1))<i)|>Seq.fold(fun n g->fn (n,(i&&&(1<<<g)>0)))(0,0)) > 1 then Some(i) else None) |
{5..(1<<<n)-1}|>Seq.choose(fun i->if fst({0..n-1}|>Seq.takeWhile(fun n->(1<<<(n-1))<i)|>Seq.fold(fun n g->fn (n,(i&&&(1<<<g)>0)))(0,0)) > 1 then Some(i) else None) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Again counting the number of non-continuous subsequences |
Again counting the number of non-continuous subsequences |
||
<pre> |
<pre> |
||
Line 1,012: | Line 1,012: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
< |
<syntaxhighlight lang="freebasic">Sub Subsecuencias_no_continuas(l() As String) |
||
Dim As Integer i, j, g, n, r, s, w |
Dim As Integer i, j, g, n, r, s, w |
||
Dim As String a, b, c |
Dim As String a, b, c |
||
Line 1,044: | Line 1,044: | ||
Print "Para [e, r, n, i, t] las subsecuencias no continuas son:" |
Print "Para [e, r, n, i, t] las subsecuencias no continuas son:" |
||
Subsecuencias_no_continuas(lista2()) |
Subsecuencias_no_continuas(lista2()) |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,075: | Line 1,075: | ||
=={{header|Go}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,113: | Line 1,113: | ||
fmt.Println(" ", s) |
fmt.Println(" ", s) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,128: | Line 1,128: | ||
===Generalized monadic filter=== |
===Generalized monadic filter=== |
||
< |
<syntaxhighlight lang="haskell">action p x = if p x then succ x else x |
||
fenceM p q s [] = guard (q s) >> return [] |
fenceM p q s [] = guard (q s) >> return [] |
||
Line 1,136: | Line 1,136: | ||
return $ f x ys |
return $ f x ys |
||
ncsubseq = fenceM [((:), action even), (flip const, action odd)] (>= 3) 0</ |
ncsubseq = fenceM [((:), action even), (flip const, action odd)] (>= 3) 0</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,150: | Line 1,150: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="haskell">continuous = null . dropWhile not . dropWhile id . dropWhile not |
||
ncs xs = map (map fst . filter snd . zip xs) $ |
ncs xs = map (map fst . filter snd . zip xs) $ |
||
filter (not . continuous) $ |
filter (not . continuous) $ |
||
mapM (const [True,False]) xs</ |
mapM (const [True,False]) xs</syntaxhighlight> |
||
===Recursive=== |
===Recursive=== |
||
Recursive method with powerset as helper function. |
Recursive method with powerset as helper function. |
||
< |
<syntaxhighlight lang="haskell">import Data.List |
||
poset = foldr (\x p -> p ++ map (x:) p) [[]] |
poset = foldr (\x p -> p ++ map (x:) p) [[]] |
||
Line 1,167: | Line 1,167: | ||
nc [_] [] = [[]] |
nc [_] [] = [[]] |
||
nc (_:x:xs) [] = nc [x] xs |
nc (_:x:xs) [] = nc [x] xs |
||
nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)</ |
nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,187: | Line 1,187: | ||
A disjointed subsequence is a consecutive subsequence followed by a gap, |
A disjointed subsequence is a consecutive subsequence followed by a gap, |
||
then by any nonempty subsequence to its right: |
then by any nonempty subsequence to its right: |
||
< |
<syntaxhighlight lang="haskell">import Data.List (subsequences, tails, delete) |
||
disjoint a = concatMap (cutAt a) [1..length a - 2] where |
disjoint a = concatMap (cutAt a) [1..length a - 2] where |
||
Line 1,194: | Line 1,194: | ||
(left, _:right) = splitAt n s |
(left, _:right) = splitAt n s |
||
main = print $ length $ disjoint [1..20]</ |
main = print $ length $ disjoint [1..20]</syntaxhighlight> |
||
Build a lexicographic list of consecutive subsequences, |
Build a lexicographic list of consecutive subsequences, |
||
and a list of all subsequences, then subtract one from the other: |
and a list of all subsequences, then subtract one from the other: |
||
< |
<syntaxhighlight lang="haskell">import Data.List (inits, tails) |
||
subseqs = foldr (\x s -> [x] : map (x:) s ++ s) [] |
subseqs = foldr (\x s -> [x] : map (x:) s ++ s) [] |
||
Line 1,211: | Line 1,211: | ||
disjoint s = (subseqs s) `minus` (consecs s) |
disjoint s = (subseqs s) `minus` (consecs s) |
||
main = mapM_ print $ disjoint [1..4]</ |
main = mapM_ print $ disjoint [1..4]</syntaxhighlight> |
||
=={{header|J}}== |
=={{header|J}}== |
||
We select those combinations where the end of the first continuous subsequence appears before the start of the last continuous subsequence: |
We select those combinations where the end of the first continuous subsequence appears before the start of the last continuous subsequence: |
||
< |
<syntaxhighlight lang="j">allmasks=: 2 #:@i.@^ # |
||
firstend=:1 0 i.&1@E."1 ] |
firstend=:1 0 i.&1@E."1 ] |
||
laststart=: 0 1 {:@I.@E."1 ] |
laststart=: 0 1 {:@I.@E."1 ] |
||
noncont=: <@#~ (#~ firstend < laststart)@allmasks</ |
noncont=: <@#~ (#~ firstend < laststart)@allmasks</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> noncont 1+i.4 |
||
┌───┬───┬───┬─────┬─────┐ |
┌───┬───┬───┬─────┬─────┐ |
||
│2 4│1 4│1 3│1 3 4│1 2 4│ |
│2 4│1 4│1 3│1 3 4│1 2 4│ |
||
Line 1,231: | Line 1,231: | ||
└──┴──┴──┴───┴───┴──┴──┴───┴──┴───┴───┴────┴───┴───┴────┴────┘ |
└──┴──┴──┴───┴───┴──┴──┴───┴──┴───┴───┴────┴───┴───┴────┴────┘ |
||
#noncont i.10 |
#noncont i.10 |
||
968</ |
968</syntaxhighlight> |
||
Alternatively, since there are relatively few continuous sequences, we could specifically exclude them: |
Alternatively, since there are relatively few continuous sequences, we could specifically exclude them: |
||
< |
<syntaxhighlight lang="j">contmasks=: a: ;@, 1 <:/~@i.&.>@i.@+ # |
||
noncont=: <@#~ (allmasks -. contmasks)</ |
noncont=: <@#~ (allmasks -. contmasks)</syntaxhighlight> |
||
(we get the same behavior from this implementation) |
(we get the same behavior from this implementation) |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">public class NonContinuousSubsequences { |
||
public static void main(String args[]) { |
public static void main(String args[]) { |
||
Line 1,256: | Line 1,256: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>12 4 |
<pre>12 4 |
||
Line 1,268: | Line 1,268: | ||
{{works with|SpiderMonkey}} |
{{works with|SpiderMonkey}} |
||
< |
<syntaxhighlight lang="javascript">function non_continuous_subsequences(ary) { |
||
var non_continuous = new Array(); |
var non_continuous = new Array(); |
||
for (var i = 0; i < ary.length; i++) { |
for (var i = 0; i < ary.length; i++) { |
||
Line 1,291: | Line 1,291: | ||
load('json2.js'); /* http://www.json.org/js.html */ |
load('json2.js'); /* http://www.json.org/js.html */ |
||
print(JSON.stringify( non_continuous_subsequences( powerset([1,2,3,4]))));</ |
print(JSON.stringify( non_continuous_subsequences( powerset([1,2,3,4]))));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,305: | Line 1,305: | ||
subsets, we will use the powerset approach, and accordingly begin by |
subsets, we will use the powerset approach, and accordingly begin by |
||
defining subsets/0 as a generator. |
defining subsets/0 as a generator. |
||
< |
<syntaxhighlight lang="jq"># Generate a stream of subsets of the input array |
||
def subsets: |
def subsets: |
||
if length == 0 then [] |
if length == 0 then [] |
||
Line 1,320: | Line 1,320: | ||
def non_continuous_subsequences: |
def non_continuous_subsequences: |
||
(length | non_continuous_indices) as $ix |
(length | non_continuous_indices) as $ix |
||
| [.[ $ix[] ]] ;</ |
| [.[ $ix[] ]] ;</syntaxhighlight> |
||
'''Example''': |
'''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]. |
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]. |
||
< |
<syntaxhighlight lang="jq">def count(f): reduce f as $i (0; . + 1); |
||
count( [range(0;20)] | non_continuous_subsequences) |
count( [range(0;20)] | non_continuous_subsequences) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
$ jq -n -f powerset_generator.jq |
$ jq -n -f powerset_generator.jq |
||
Line 1,339: | Line 1,339: | ||
'''Iterator and Functions''' |
'''Iterator and Functions''' |
||
< |
<syntaxhighlight lang="julia">using Printf, IterTools |
||
import Base.IteratorSize, Base.iterate, Base.length |
import Base.IteratorSize, Base.iterate, Base.length |
||
Line 1,397: | Line 1,397: | ||
@printf "%7d → %d\n" x length(NCSubSeq(x)) |
@printf "%7d → %d\n" x length(NCSubSeq(x)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Testing NCSubSeq for 4 items: |
Testing NCSubSeq for 4 items: |
||
Line 1,446: | Line 1,446: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
fun <T> ncs(a: Array<T>) { |
fun <T> ncs(a: Array<T>) { |
||
Line 1,478: | Line 1,478: | ||
val ca = arrayOf('a', 'b', 'c', 'd', 'e') |
val ca = arrayOf('a', 'b', 'c', 'd', 'e') |
||
ncs(ca) |
ncs(ca) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,507: | Line 1,507: | ||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
<syntaxhighlight lang="m2000 interpreter"> |
|||
<lang M2000 Interpreter> |
|||
Module Non_continuous_subsequences (item$(), display){ |
Module Non_continuous_subsequences (item$(), display){ |
||
Function positions(n) { |
Function positions(n) { |
||
Line 1,558: | Line 1,558: | ||
Non_continuous_subsequences ("1","2","3","4","5","6","7","8","9","0"), false |
Non_continuous_subsequences ("1","2","3","4","5","6","7","8","9","0"), false |
||
clipboard doc$ |
clipboard doc$ |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,691: | Line 1,691: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
We make all the subsets then filter out the continuous ones: |
We make all the subsets then filter out the continuous ones: |
||
< |
<syntaxhighlight lang="mathematica">GoodBad[i_List]:=Not[MatchQ[Differences[i],{1..}|{}]] |
||
n=5 |
n=5 |
||
Select[Subsets[Range[n]],GoodBad]</ |
Select[Subsets[Range[n]],GoodBad]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{{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}}</pre> |
<pre>{{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}}</pre> |
||
Line 1,699: | Line 1,699: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">import sequtils |
||
proc ncsub[T](se: seq[T], s = 0): seq[seq[T]] = |
proc ncsub[T](se: seq[T], s = 0): seq[seq[T]] = |
||
Line 1,717: | Line 1,717: | ||
echo "ncsub(", toSeq 1.. 3, ") = ", ncsub(toSeq 1..3) |
echo "ncsub(", toSeq 1.. 3, ") = ", ncsub(toSeq 1..3) |
||
echo "ncsub(", toSeq 1.. 4, ") = ", ncsub(toSeq 1..4) |
echo "ncsub(", toSeq 1.. 4, ") = ", ncsub(toSeq 1..4) |
||
echo "ncsub(", toSeq 1.. 5, ") = ", ncsub(toSeq 1..5)</ |
echo "ncsub(", toSeq 1.. 5, ") = ", ncsub(toSeq 1..5)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>ncsub(@[1, 2, 3]) = @[@[1, 3]] |
<pre>ncsub(@[1, 2, 3]) = @[@[1, 3]] |
||
Line 1,727: | Line 1,727: | ||
{{trans|Generalized monadic filter}} |
{{trans|Generalized monadic filter}} |
||
< |
<syntaxhighlight lang="ocaml">let rec fence s = function |
||
[] -> |
[] -> |
||
if s >= 3 then |
if s >= 3 then |
||
Line 1,748: | Line 1,748: | ||
fence (s + 1) xs |
fence (s + 1) xs |
||
let ncsubseq = fence 0</ |
let ncsubseq = fence 0</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,763: | Line 1,763: | ||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
A nice application of finite set constraints. We just describe what we want and the constraint system will deliver it: |
A nice application of finite set constraints. We just describe what we want and the constraint system will deliver it: |
||
< |
<syntaxhighlight lang="oz">declare |
||
fun {NCSubseq SeqList} |
fun {NCSubseq SeqList} |
||
Seq = {FS.value.make SeqList} |
Seq = {FS.value.make SeqList} |
||
Line 1,787: | Line 1,787: | ||
end |
end |
||
in |
in |
||
{Inspect {NCSubseq [1 2 3 4]}}</ |
{Inspect {NCSubseq [1 2 3 4]}}</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{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.) |
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.) |
||
< |
<syntaxhighlight lang="parigp">noncontig(n)=n>>=valuation(n,2);n++;n>>=valuation(n,2);n>1; |
||
nonContigSubseq(v)={ |
nonContigSubseq(v)={ |
||
for(i=5,2^#v-1, |
for(i=5,2^#v-1, |
||
Line 1,800: | Line 1,800: | ||
}; |
}; |
||
nonContigSubseq([1,2,3]) |
nonContigSubseq([1,2,3]) |
||
nonContigSubseq(["a","b","c","d","e"])</ |
nonContigSubseq(["a","b","c","d","e"])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 3] |
<pre>[1, 3] |
||
Line 1,822: | Line 1,822: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">my ($max, @current); |
||
sub non_continuous { |
sub non_continuous { |
||
my ($idx, $has_gap) = @_; |
my ($idx, $has_gap) = @_; |
||
Line 1,839: | Line 1,839: | ||
$max = 20; |
$max = 20; |
||
print "found ", non_continuous(1), " sequences\n";</ |
print "found ", non_continuous(1), " sequences\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>found 1048365 sequences</pre> |
<pre>found 1048365 sequences</pre> |
||
Line 1,847: | Line 1,847: | ||
mean non-contiguous until you actually take something later.<br> |
mean non-contiguous until you actually take something later.<br> |
||
Counts non-contiguous subsequences of sequences of length 1..20 in under half a second |
Counts non-contiguous subsequences of sequences of length 1..20 in under half a second |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
||
Line 1,880: | Line 1,880: | ||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,898: | Line 1,898: | ||
This approach uses <code>power_set/1</code> (from the <code>util</code> module) to get the proper indices. |
This approach uses <code>power_set/1</code> (from the <code>util</code> module) to get the proper indices. |
||
< |
<syntaxhighlight lang="picat">import util. |
||
go => |
go => |
||
Line 1,919: | Line 1,919: | ||
% get all the index positions that are non-continuous |
% get all the index positions that are non-continuous |
||
non_cont_ixs(N) = [ P: P in power_set(1..N), length(P) > 1, P.last() - P.first() != P.length-1].</ |
non_cont_ixs(N) = [ P: P in power_set(1..N), length(P) > 1, P.last() - P.first() != P.length-1].</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,952: | Line 1,952: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
{{trans|Scheme}} |
{{trans|Scheme}} |
||
< |
<syntaxhighlight lang="picolisp">(de ncsubseq (Lst) |
||
(let S 0 |
(let S 0 |
||
(recur (S Lst) |
(recur (S Lst) |
||
Line 1,966: | Line 1,966: | ||
(mapcar '((YS) (cons X YS)) |
(mapcar '((YS) (cons X YS)) |
||
(recurse S XS) ) |
(recurse S XS) ) |
||
(recurse (inc S) XS) ) ) ) ) ) ) )</ |
(recurse (inc S) XS) ) ) ) ) ) ) )</syntaxhighlight> |
||
=={{header|Pop11}}== |
=={{header|Pop11}}== |
||
Line 1,973: | Line 1,973: | ||
variables to keep track if subsequence is continuous. |
variables to keep track if subsequence is continuous. |
||
< |
<syntaxhighlight lang="pop11">define ncsubseq(l); |
||
lvars acc = [], gap_started = false, is_continuous = true; |
lvars acc = [], gap_started = false, is_continuous = true; |
||
define do_it(l1, l2); |
define do_it(l1, l2); |
||
Line 1,996: | Line 1,996: | ||
enddefine; |
enddefine; |
||
ncsubseq([1 2 3 4 5]) =></ |
ncsubseq([1 2 3 4 5]) =></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,003: | Line 2,003: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
< |
<syntaxhighlight lang="powershell">Function SubSequence ( [Array] $S, [Boolean] $all=$false ) |
||
{ |
{ |
||
$sc = $S.count |
$sc = $S.count |
||
Line 2,071: | Line 2,071: | ||
} |
} |
||
( NonContinuous-SubSequence 'a','b','c','d','e' ) | Select-Object length, @{Name='value';Expression={ $_ } } | Sort-Object length, value | ForEach-Object { $_.value }</ |
( NonContinuous-SubSequence 'a','b','c','d','e' ) | Select-Object length, @{Name='value';Expression={ $_ } } | Sort-Object length, value | ForEach-Object { $_.value }</syntaxhighlight> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Line 2,077: | Line 2,077: | ||
We explain to Prolog how to build a non continuous subsequence of a list L, then we ask Prolog to fetch all the subsequences. |
We explain to Prolog how to build a non continuous subsequence of a list L, then we ask Prolog to fetch all the subsequences. |
||
<syntaxhighlight lang="prolog"> |
|||
<lang Prolog> |
|||
% fetch all the subsequences |
% fetch all the subsequences |
||
ncsubs(L, LNCSL) :- |
ncsubs(L, LNCSL) :- |
||
Line 2,103: | Line 2,103: | ||
reverse(L, [_|SL1]), |
reverse(L, [_|SL1]), |
||
reverse(SL1, SL)). |
reverse(SL1, SL)). |
||
</syntaxhighlight> |
|||
</lang> |
|||
Example : |
Example : |
||
< |
<syntaxhighlight lang="prolog">?- ncsubs([a,e,i,o,u], L). |
||
L = [[a,e,i,u],[a,e,o],[a,e,o,u],[a,e,u],[a,i],[a,i,o],[a,i,o,u],[a,i,u],[a,o],[a,o,u],[a,u],[e,i,u],[e,o],[e,o,u],[e,u],[i,u]]</ |
L = [[a,e,i,u],[a,e,o],[a,e,o,u],[a,e,u],[a,i],[a,i,o],[a,i,o,u],[a,i,u],[a,o],[a,o,u],[a,u],[e,i,u],[e,o],[e,o,u],[e,u],[i,u]]</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|Scheme}} |
{{trans|Scheme}} |
||
< |
<syntaxhighlight lang="python">def ncsub(seq, s=0): |
||
if seq: |
if seq: |
||
x = seq[:1] |
x = seq[:1] |
||
Line 2,119: | Line 2,119: | ||
return [x + ys for ys in ncsub(xs, s + p1)] + ncsub(xs, s + p2) |
return [x + ys for ys in ncsub(xs, s + p1)] + ncsub(xs, s + p2) |
||
else: |
else: |
||
return [[]] if s >= 3 else []</ |
return [[]] if s >= 3 else []</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,133: | Line 2,133: | ||
A faster Python + Psyco JIT version: |
A faster Python + Psyco JIT version: |
||
< |
<syntaxhighlight lang="python">from sys import argv |
||
import psyco |
import psyco |
||
Line 2,172: | Line 2,172: | ||
psyco.full() |
psyco.full() |
||
n = 10 if len(argv) < 2 else int(argv[1]) |
n = 10 if len(argv) < 2 else int(argv[1]) |
||
print len( ncsub(range(1, n)) )</ |
print len( ncsub(range(1, n)) )</syntaxhighlight> |
||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
Line 2,178: | Line 2,178: | ||
A sequence of n items has 2^n possible subsequences, including the empty sequence. These correspond to the numbers 0 to 2^n-1, where a one in the binary expansion of the number indicates inclusion in the subsequence of the corresponding item in the sequence. Non-continuous subsequences correspond to numbers where the binary expansion of the number has a one, followed by one or more zeroes, followed by a one. |
A sequence of n items has 2^n possible subsequences, including the empty sequence. These correspond to the numbers 0 to 2^n-1, where a one in the binary expansion of the number indicates inclusion in the subsequence of the corresponding item in the sequence. Non-continuous subsequences correspond to numbers where the binary expansion of the number has a one, followed by one or more zeroes, followed by a one. |
||
< |
<syntaxhighlight lang="quackery"> [ dup 1 & dip [ 1 >> ] ] is 2/mod ( n --> n n ) |
||
[ 0 swap |
[ 0 swap |
||
Line 2,215: | Line 2,215: | ||
' [ 1 2 3 4 ] ncsubs echo cr |
' [ 1 2 3 4 ] ncsubs echo cr |
||
$ "quackery" ncsubs 72 wrap$</ |
$ "quackery" ncsubs 72 wrap$</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,242: | Line 2,242: | ||
The idea behind this is to loop over the possible lengths of subsequence, finding all subsequences then discarding those which are continuous. |
The idea behind this is to loop over the possible lengths of subsequence, finding all subsequences then discarding those which are continuous. |
||
< |
<syntaxhighlight lang="r">ncsub <- function(x) |
||
{ |
{ |
||
n <- length(x) |
n <- length(x) |
||
Line 2,258: | Line 2,258: | ||
# Example usage |
# Example usage |
||
ncsub(1:4) |
ncsub(1:4) |
||
ncsub(letters[1:5])</ |
ncsub(letters[1:5])</syntaxhighlight> |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Take a simple <tt>subsets</tt> definition: |
Take a simple <tt>subsets</tt> definition: |
||
< |
<syntaxhighlight lang="racket"> |
||
(define (subsets l) |
(define (subsets l) |
||
(if (null? l) '(()) |
(if (null? l) '(()) |
||
(append (for/list ([l2 (subsets (cdr l))]) (cons (car l) l2)) |
(append (for/list ([l2 (subsets (cdr l))]) (cons (car l) l2)) |
||
(subsets (cdr l))))) |
(subsets (cdr l))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
since the subsets are returned in their original order, it is also a sub-sequences function. |
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. |
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. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(define (non-continuous-subseqs l) |
(define (non-continuous-subseqs l) |
||
Line 2,283: | Line 2,283: | ||
(non-continuous-subseqs '(1 2 3 4)) |
(non-continuous-subseqs '(1 2 3 4)) |
||
;; => '((1 2 4) (1 3 4) (1 3) (1 4) (2 4)) |
;; => '((1 2 4) (1 3 4) (1 3) (1 4) (2 4)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{works with|rakudo|2015-09-24}} |
{{works with|rakudo|2015-09-24}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub non_continuous_subsequences ( *@list ) { |
||
@list.combinations.grep: { 1 != all( .[ 0 ^.. .end] Z- .[0 ..^ .end] ) } |
@list.combinations.grep: { 1 != all( .[ 0 ^.. .end] Z- .[0 ..^ .end] ) } |
||
} |
} |
||
Line 2,294: | Line 2,294: | ||
say non_continuous_subsequences( 1..3 )».gist; |
say non_continuous_subsequences( 1..3 )».gist; |
||
say non_continuous_subsequences( 1..4 )».gist; |
say non_continuous_subsequences( 1..4 )».gist; |
||
say non_continuous_subsequences( ^4 ).map: {[<a b c d>[.list]].gist};</ |
say non_continuous_subsequences( ^4 ).map: {[<a b c d>[.list]].gist};</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>((1 3)) |
<pre>((1 3)) |
||
Line 2,302: | Line 2,302: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
This REXX version also works with non-numeric (alphabetic) items (as well as numbers). |
This REXX version also works with non-numeric (alphabetic) items (as well as numbers). |
||
< |
<syntaxhighlight lang="rexx">/*REXX program lists all the non─continuous subsequences (NCS), given a sequence. */ |
||
parse arg list /*obtain optional argument from the CL.*/ |
parse arg list /*obtain optional argument from the CL.*/ |
||
if list='' | list=="," then list= 1 2 3 4 5 /*Not specified? Then use the default.*/ |
if list='' | list=="," then list= 1 2 3 4 5 /*Not specified? Then use the default.*/ |
||
Line 2,334: | Line 2,334: | ||
exit 0 /*stick a fork in it, we're all done. */ |
exit 0 /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
s: if arg(1)==1 then return ''; return word( arg(2) 's', 1) /*simple pluralizer.*/</ |
s: if arg(1)==1 then return ''; return word( arg(2) 's', 1) /*simple pluralizer.*/</syntaxhighlight> |
||
{{out|output|text= when using the input of: <tt> 1 2 3 4 </tt>}} |
{{out|output|text= when using the input of: <tt> 1 2 3 4 </tt>}} |
||
<pre> |
<pre> |
||
Line 2,444: | Line 2,444: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Non-continuous subsequences |
# Project : Non-continuous subsequences |
||
Line 2,503: | Line 2,503: | ||
next |
next |
||
return items |
return items |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,537: | Line 2,537: | ||
Uses code from [[Power Set]]. |
Uses code from [[Power Set]]. |
||
< |
<syntaxhighlight lang="ruby">class Array |
||
def func_power_set |
def func_power_set |
||
inject([[]]) { |ps,item| # for each item in the Array |
inject([[]]) { |ps,item| # for each item in the Array |
||
Line 2,558: | Line 2,558: | ||
p (1..4).to_a.non_continuous_subsequences |
p (1..4).to_a.non_continuous_subsequences |
||
p (1..5).to_a.non_continuous_subsequences |
p (1..5).to_a.non_continuous_subsequences |
||
p ("a".."d").to_a.non_continuous_subsequences</ |
p ("a".."d").to_a.non_continuous_subsequences</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,568: | Line 2,568: | ||
</pre> |
</pre> |
||
It is not the value of the array element and when judging continuation in the position, it changes as follows. |
It is not the value of the array element and when judging continuation in the position, it changes as follows. |
||
< |
<syntaxhighlight lang="ruby">class Array |
||
def continuous?(seq) |
def continuous?(seq) |
||
seq.each_cons(2) {|a, b| return false if index(a)+1 != index(b)} |
seq.each_cons(2) {|a, b| return false if index(a)+1 != index(b)} |
||
Line 2,575: | Line 2,575: | ||
end |
end |
||
p %w(a e i o u).non_continuous_subsequences</ |
p %w(a e i o u).non_continuous_subsequences</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,581: | Line 2,581: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">object NonContinuousSubSequences extends App { |
||
private def seqR(s: String, c: String, i: Int, added: Int): Unit = { |
private def seqR(s: String, c: String, i: Int, added: Int): Unit = { |
||
Line 2,593: | Line 2,593: | ||
seqR("1234", "", 0, 0) |
seqR("1234", "", 0, 0) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{trans|Generalized monadic filter}} |
{{trans|Generalized monadic filter}} |
||
< |
<syntaxhighlight lang="scheme">(define (ncsubseq lst) |
||
(let recurse ((s 0) |
(let recurse ((s 0) |
||
(lst lst)) |
(lst lst)) |
||
Line 2,614: | Line 2,614: | ||
(map (lambda (ys) (cons x ys)) |
(map (lambda (ys) (cons x ys)) |
||
(recurse s xs)) |
(recurse s xs)) |
||
(recurse (+ s 1) xs)))))))</ |
(recurse (+ s 1) xs)))))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,625: | Line 2,625: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func array bitset: ncsub (in bitset: seq, in integer: s) is func |
const func array bitset: ncsub (in bitset: seq, in integer: s) is func |
||
Line 2,654: | Line 2,654: | ||
writeln(seq); |
writeln(seq); |
||
end for; |
end for; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,667: | Line 2,667: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="ruby">func non_continuous(min, max, subseq=[], has_gap=false) { |
||
static current = []; |
static current = []; |
||
Line 2,684: | Line 2,684: | ||
say non_continuous(1, 3); |
say non_continuous(1, 3); |
||
say non_continuous(1, 4); |
say non_continuous(1, 4); |
||
say non_continuous("a", "d");</ |
say non_continuous("a", "d");</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,696: | Line 2,696: | ||
{{trans|Generalized monadic filter}} |
{{trans|Generalized monadic filter}} |
||
< |
<syntaxhighlight lang="sml">fun fence s [] = |
||
if s >= 3 then |
if s >= 3 then |
||
[[]] |
[[]] |
||
Line 2,716: | Line 2,716: | ||
fence (s + 1) xs |
fence (s + 1) xs |
||
fun ncsubseq xs = fence 0 xs</ |
fun ncsubseq xs = fence 0 xs</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,731: | Line 2,731: | ||
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'': |
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'': |
||
< |
<syntaxhighlight lang="tcl"> proc subsets l { |
||
set res [list [list]] |
set res [list [list]] |
||
foreach e $l { |
foreach e $l { |
||
Line 2,753: | Line 2,753: | ||
% lfilter is_not_continuous [subsets {1 2 3 4}] |
% 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}</syntaxhighlight> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
Line 2,759: | Line 2,759: | ||
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 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). |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
noncontinuous = num; ^rlK3ZK17rSS/~& powerset |
noncontinuous = num; ^rlK3ZK17rSS/~& powerset |
||
Line 2,765: | Line 2,765: | ||
#show+ |
#show+ |
||
examples = noncontinuous 'abcde'</ |
examples = noncontinuous 'abcde'</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,787: | Line 2,787: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
< |
<syntaxhighlight lang="vb">'Non-continuous subsequences - VBScript - 03/02/2021 |
||
Function noncontsubseq(l) |
Function noncontsubseq(l) |
||
Line 2,819: | Line 2,819: | ||
WScript.Echo "List: [" & Join(list, ", ") & "]" |
WScript.Echo "List: [" & Join(list, ", ") & "]" |
||
nn = noncontsubseq(list) |
nn = noncontsubseq(list) |
||
WScript.Echo nn & " non-continuous subsequences" </ |
WScript.Echo nn & " non-continuous subsequences" </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,835: | Line 2,835: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Needed a bit of doctoring to do the character example as Wren only has strings. |
Needed a bit of doctoring to do the character example as Wren only has strings. |
||
< |
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt |
||
var ncs = Fn.new { |a| |
var ncs = Fn.new { |a| |
||
Line 2,870: | Line 2,870: | ||
System.print() |
System.print() |
||
var ca = ["a", "b", "c", "d", "e"] |
var ca = ["a", "b", "c", "d", "e"] |
||
ncs.call(ca)</ |
ncs.call(ca)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,900: | Line 2,900: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|JavaScript}} |
{{trans|JavaScript}} |
||
< |
<syntaxhighlight lang="zkl">fcn non_continuous_subsequences(ary){ |
||
pwerSet(ary).filter(fcn(list){(not isContinuous(list)) }) |
pwerSet(ary).filter(fcn(list){(not isContinuous(list)) }) |
||
} |
} |
||
Line 2,908: | Line 2,908: | ||
return(True); |
return(True); |
||
} |
} |
||
non_continuous_subsequences(T(1,2,3,4)).println();</ |
non_continuous_subsequences(T(1,2,3,4)).println();</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">fcn pwerSet(list){ |
||
(0).pump(list.len(),List,List,Utils.Helpers.pickNFrom.fp1(list), |
(0).pump(list.len(),List,List,Utils.Helpers.pickNFrom.fp1(list), |
||
T(T,Void.Write,Void.Write) ) .append(list) |
T(T,Void.Write,Void.Write) ) .append(list) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">fcn brokenSubsequences(str){ |
||
pwerSet(str.split("")).apply("concat") |
pwerSet(str.split("")).apply("concat") |
||
.filter('wrap(substr){ (not str.holds(substr)) }) |
.filter('wrap(substr){ (not str.holds(substr)) }) |
||
} |
} |
||
brokenSubsequences("1234").println();</ |
brokenSubsequences("1234").println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |