Non-continuous subsequences: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(jq) |
m (→{{header|Wren}}: Minor tidy) |
||
(48 intermediate revisions by 29 users not shown) | |||
Line 6:
A ''continuous'' subsequence is one in which no elements are missing between the first and last elements of the subsequence.
Note: Subsequences are defined ''structurally'', not by their contents.
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.
'''Task''': Find all non-continuous subsequences for a given sequence.
;Example:
For the sequence ''1,2,3,4'', there are five non-continuous subsequences, namely:
::::* ''1,3''
::::* ''1,4''
::::* ''2,4''
::::* ''1,3,4''
::::* ''1,2,4''
;Goal:
There are different ways to calculate those subsequences.
Demonstrate algorithm(s) that are natural for the language.
{{Template:Strings}}
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F ncsub(seq, s = 0)
I seq.empty
R I s >= 3 {[[Int]()]} E [[Int]]()
E
V x = seq[0.<1]
V xs = seq[1..]
V p2 = s % 2
V p1 = !p2
R ncsub(xs, s + p1).map(ys -> @x + ys) [+] ncsub(xs, s + p2)
print(ncsub(Array(1..3)))
print(ncsub(Array(1..4)))
print(ncsub(Array(1..5)))</syntaxhighlight>
{{out}}
<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>
=={{header|Ada}}==
===Recursive===
<
procedure Test_Non_Continuous is
Line 50 ⟶ 92:
Put_NCS ((1,2,3,4)); New_Line;
Put_NCS ((1,2,3,4,5)); New_Line;
end Test_Non_Continuous;</
{{out}}
<pre style="height:30ex;overflow:scroll"> 1 3
Line 78 ⟶ 119:
2 5
3 5</pre>
=={{header|ALGOL 68}}==
===Recursive===
Line 85 ⟶ 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]}}
<
MODE SEQMODE = CHAR;
MODE SEQ = [1:0]SEQMODE;
Line 119 ⟶ 161:
print((seq, new line))
# OD # )
END; test non continuous</
{{out}}
<pre>
aeiu
Line 149 ⟶ 191:
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;
Line 195 ⟶ 237:
print((seq, new line))
# OD # )
)</
{{out}}
<pre>
iu
Line 220 ⟶ 262:
ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?p=277328#277328 discussion]
<
MsgBox % noncontinuous("1,2,3,4", ",")
Line 239 ⟶ 281:
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:"
Line 274 ⟶ 316:
NEXT g%
NEXT s%
ENDPROC</
{{out}}
<pre>
For [1, 2, 3, 4] non-continuous subsequences are:
Line 303 ⟶ 345:
=={{header|Bracmat}}==
<
= sub
. ( sub
Line 323 ⟶ 365:
& noncontinuous$(e r n i t)
);
</syntaxhighlight>
{{out}}
<pre>e n t
e n
Line 344 ⟶ 386:
=={{header|C}}==
Note: This specimen can only handle lists of length less than the number of bits in an '''int'''.
<
#include <stdio.h>
Line 363 ⟶ 405:
return 0;
}</
Example use:
<pre>
Line 377 ⟶ 419:
Using "consecutive + gap + any subsequence" to produce disjointed sequences:
<
#include <stdio.h>
#include <stdlib.h>
Line 401 ⟶ 443:
return 0;
}</
===Recursive method===
Using recursion and a state transition table.
<
typedef unsigned char sint;
Line 454 ⟶ 496:
pick(c - 1, 0, s_blnk, v + 1, 0);
return 0;
}</
<pre>% ./a.out 1 2 3 4
1 3
Line 464 ⟶ 506:
968</pre>
=={{header|C
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
public static void Main() {
var sequence = new[] { "A", "B", "C", "D" };
foreach (var subset in Subsets(sequence.Length).Where(s => !IsContinuous(s))) {
Console.WriteLine(string.Join(" ", subset.Select(i => sequence[i])));
}
}
static IEnumerable<List<int>> Subsets(int length) {
int[] values = Enumerable.Range(0, length).ToArray();
var stack = new Stack<int>(length);
for (int i = 0; stack.Count > 0 || i < length; ) {
if (i < length) {
stack.Push(i++);
yield return (from index in stack.Reverse() select values[index]).ToList();
} else {
i = stack.Pop() + 1;
if (stack.Count > 0) i = stack.Pop() + 1;
}
}
}
static bool IsContinuous(List<int> list) => list[list.Count - 1] - list[0] + 1 == list.Count;
}</syntaxhighlight>
{{out}}
<pre>
A C
A D
B D
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">
/*
* Nigel Galloway, July 19th., 2017 - Yes well is this any better?
*/
class N{
uint n,i,g,e,l;
public:
N(uint n): n(n-1),i{},g{},e(1),l(n-1){}
bool hasNext(){
g=(1<<n)+e;for(i=l;i<n;++i) g+=1<<i;
if (l==2) {l=--n; e=1; return true;}
if (e<((1<<(l-1))-1)) {++e; return true;}
e=1; --l; return (l>0);
}
uint next() {return g;}
};
</syntaxhighlight>
Which may be used as follows:
<syntaxhighlight lang="cpp">
int main(){
N n(4);
while (n.hasNext()) std::cout << n.next() << "\t* " << std::bitset<4>(n.next()) << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
9 * 1001
10 * 1010
11 * 1011
13 * 1101
5 * 0101
</pre>
I can count the length of the sequence:
<syntaxhighlight lang="cpp">
int main(){
N n(31);
int z{};for (;n.hasNext();++z); std::cout << z << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
2147483151
</pre>
=={{header|Clojure}}==
Line 546 ⟶ 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:
<
(use '[clojure.contrib.combinatorics :only (subsets)])
Line 563 ⟶ 612:
(filter (of-min-length 2) (non-continuous-subsequences [:a :b :c :d]))
</syntaxhighlight>
=={{header|CoffeeScript}}==
Use binary bitmasks to enumerate our sequences.
<
is_contigous_binary = (n) ->
# return true if binary representation of n is
Line 625 ⟶ 674:
num_solutions = non_contig_subsequences(arr).length
console.log "for n=#{n} there are #{num_solutions} solutions"
</syntaxhighlight>
{{out}}
<
> coffee non_contig_subseq.coffee
[ [ 1, 3 ],
Line 645 ⟶ 694:
for n=9 there are 466 solutions
for n=10 there are 968 solutions
</
=={{header|Common Lisp}}==
Line 653 ⟶ 702:
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
Line 673 ⟶ 722:
(map-into subsequence-d 'first subsequence-d)))
(let ((nc-subsequences (delete-if #'continuous-p (subsequences list))))
(map-into nc-subsequences #'designated-sequence nc-subsequences))))</
{{trans|Scheme}}
<
(labels ((recurse (s list)
(if (endp list)
Line 692 ⟶ 741:
(recurse s xs))
(recurse (+ s 1) xs)))))))
(recurse 0 list)))</
=={{header|D}}==
===Recursive Version===
{{trans|Python}}
<syntaxhighlight lang="d">T[][] ncsub(T)(in T[] seq, in uint s=0) pure nothrow @safe {
if (seq.length) {
foreach (ys; ncsub(seq[1 .. $], s + !(s % 2)))
aux ~= seq[0] ~ ys;
return aux ~ ncsub(seq[1 .. $], s + s % 2);
} else
return new
}
void main() @safe {
import std.stdio;
[1, 2, 3,
foreach (const nc; [1, 2, 3, 4, 5].ncsub)
nc.writeln;
}</syntaxhighlight>
{{out}}
<pre>[[1, 3]]
Line 734 ⟶ 783:
[2, 5]
[3, 5]</pre>
===Faster Lazy Version===
This version doesn't copy the sub-arrays.
<
T[] seq;
int opApply(int delegate(ref
immutable
int result;
auto S = new
OUTER: foreach (immutable i; 1 .. 1 << n) {
bool nc = false;
foreach (immutable j; 0 ..
immutable
if (k == 0) {
if (nc) {
auto auxS = S[0 ..
result = dg(auxS);
if (result)
break
}
break;
} else if (k % 2) {
S[
} else if (
nc = true;
}
Line 772 ⟶ 821:
void main() {
import std.array, std.range;
//assert(24.iota.array.Ncsub!int.walkLength == 16_776_915);
uint counter = 0;
foreach (s; Ncsub!int(r))
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.
<syntaxhighlight lang="d">import std.stdio, std.array, std.range, std.concurrency;
Generator!(T[]) ncsub(T)(in T[] seq) {
return new typeof(return)({
immutable n = seq.length;
auto S = new T[n];
foreach (immutable i; 1 .. 1 << n) {
uint lenS = 0;
bool nc = false;
foreach (immutable j; 0 .. n + 1) {
immutable k = i >> j;
if (k == 0) {
if (nc)
yield(S[0 .. lenS]);
break;
} else if (k % 2) {
S[lenS] = seq[j];
lenS++;
} else if (lenS)
nc = true;
}
}
});
}
void main() {
assert(24.iota.array.ncsub.walkLength == 16_776_915);
[1, 2, 3].ncsub.writeln;
[1, 2, 3, 4].ncsub.writeln;
foreach (const nc; [1, 2, 3, 4, 5].ncsub)
nc.writeln;
}</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule RC do
defp masks(n) do
maxmask = trunc(:math.pow(2, n)) - 1
Enum.map(3..maxmask, &Integer.to_string(&1, 2))
|> Enum.filter_map(&contains_noncont(&1), &String.rjust(&1, n, ?0)) # padding
end
defp contains_noncont(n) do
Regex.match?(~r/10+1/, n)
end
defp apply_mask_to_list(mask, list) do
Enum.zip(to_char_list(mask), list)
|> Enum.filter_map(fn {include, _} -> include > ?0 end, fn {_, value} -> value end)
end
def ncs(list) do
Enum.map(masks(length(list)), fn mask -> apply_mask_to_list(mask, list) end)
end
end
IO.inspect RC.ncs([1,2,3])
IO.inspect RC.ncs([1,2,3,4])
IO.inspect RC.ncs('abcd')</syntaxhighlight>
{{out}}
<pre>
[[1, 3]]
[[2, 4], [1, 4], [1, 3], [1, 3, 4], [1, 2, 4]]
['bd', 'ad', 'ac', 'acd', 'abd']
</pre>
=={{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]).
Line 806 ⟶ 927:
ncs(List) ->
lists:map(fun(Mask) -> apply_mask_to_list(Mask, List) end,
masks(length(List))).</
{{out}}
<pre>
Eshell V5.10.1 (abort with ^G)
Line 816 ⟶ 937:
[[2,4],[1,4],[1,3],[1,3,4],[1,2,4]]
</pre>
=={{header|F_Sharp|F#}}==
===Generate only the non-continuous subsequences===
<syntaxhighlight lang="fsharp">
(*
A function to generate only the non-continuous subsequences.
Nigel Galloway July 20th., 2017
*)
let N n =
let fn n = Seq.map (fun g->(2<<<n)+g)
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)})
</syntaxhighlight>
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 "")
Ng 4
</syntaxhighlight>
{{out}}
<pre>
5 -> 1 3
9 -> 1 4
10 -> 2 4
11 -> 1 2 4
13 -> 1 3 4
</pre>
Counting the number of non-continuous subsequences is interesting:
<pre>
> Seq.length (N 20);;
Real: 00:00:00.169, CPU: 00:00:00.169, GC gen0: 0, gen1: 0
val it : int = 1048365
> Seq.length (N 23);;
Real: 00:00:01.238, CPU: 00:00:01.239, GC gen0: 0, gen1: 0
val it : int = 8388331
> Seq.length (N 24);;
Real: 00:00:02.520, CPU: 00:00:02.523, GC gen0: 0, gen1: 0
val it : int = 16776915
> Seq.length (N 25);;
Real: 00:00:04.926, CPU: 00:00:04.930, GC gen0: 0, gen1: 0
val it : int = 33554106
</pre>
===Generate all subsequences and filter out the continuous===
<syntaxhighlight lang="fsharp">
(*
A function to filter out continuous subsequences.
Nigel Galloway July 24th., 2017
*)
let Nonseq n=
let fn = function
|((n,0),true )->(n+1,1)
|((n,_),false)->(n,0)
|(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)
</syntaxhighlight>
Again counting the number of non-continuous subsequences
<pre>
> Seq.length (Nonseq 20);;
Real: 00:00:02.356, CPU: 00:00:02.389, GC gen0: 183, gen1: 0
val it : int = 1048365
> Seq.length (Nonseq 23);;
Real: 00:00:20.714, CPU: 00:00:20.950, GC gen0: 1571, gen1: 0
val it : int = 8388331
> Seq.length (Nonseq 24);;
Real: 00:00:43.129, CPU: 00:00:43.601, GC gen0: 3216, gen1: 0
val it : int = 16776915
> Seq.length (Nonseq 25);;
Real: 00:01:28.853, CPU: 00:01:29.869, GC gen0: 6577, gen1: 0
val it : int = 33554106
</pre>
===Conclusion===
Find a better filter or use the generator.
=={{header|FreeBASIC}}==
{{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 String a, b, c
n = Ubound(l)
For s = 0 To n-2
For g = s+1 To n-1
a = "["
For i = s To g-1
a += l(i) + ", "
Next i
For w = 1 To n-g
r = n+1-g-w
For i = 1 To 2^r-1 Step 2
b = a
For j = 0 To r-1
If i And 2^j Then b += l(g+w+j) + ", "
Next j
'Print Left(Left(b)) + "]"
c = (Left(b, Len (b)-1))
Print Left(c, Len(c)-1) + "]"
Next i
Next w
Next g
Next s
End Sub
Dim lista1(3) As String = {"1", "2", "3", "4"}
Print "Para [1, 2, 3, 4] las subsecuencias no continuas son:"
Subsecuencias_no_continuas(lista1())
Dim lista2(4) As String = {"e", "r", "n", "i", "t"}
Print "Para [e, r, n, i, t] las subsecuencias no continuas son:"
Subsecuencias_no_continuas(lista2())
Sleep</syntaxhighlight>
{{out}}
<pre>
Para [1, 2, 3, 4] las subsecuencias no continuas son:
[1, 3]
[1, 3, 4]
[1, 4]
[1, 2, 4]
[2, 4]
Para [e, r, n, i, t] las subsecuencias no continuas son:
[e, n]
[e, n, i]
[e, n, t]
[e, n, i, t]
[e, i]
[e, i, t]
[e, t]
[e, r, i]
[e, r, i, t]
[e, r, t]
[e, r, n, t]
[r, i]
[r, i, t]
[r, t]
[r, n, t]
[n, t]
</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"
Line 857 ⟶ 1,113:
fmt.Println(" ", s)
}
}</
{{out}}
<pre>
5 non-continuous subsequences:
Line 872 ⟶ 1,128:
===Generalized monadic filter===
<
fenceM p q s [] = guard (q s) >> return []
Line 880 ⟶ 1,136:
return $ f x ys
ncsubseq = fenceM [((:), action even), (flip const, action odd)] (>= 3) 0</
{{out}}
<pre>*Main> ncsubseq [1..3]
[[1,3]]
Line 895 ⟶ 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.
<
ncs xs = map (map fst . filter snd . zip xs) $
filter (not . continuous) $
mapM (const [True,False]) xs</
===Recursive===
Recursive method with powerset as helper function.
<
poset = foldr (\x p -> p ++ map (x:) p) [[]]
Line 912 ⟶ 1,167:
nc [_] [] = [[]]
nc (_:x:xs) [] = nc [x] xs
nc xs (y:ys) = (nc (xs++[y]) ys) ++ map (xs++) (tail $ poset ys)</
{{out}}
<pre>
*Main> ncsubs "aaa"
["aa"]
Line 928 ⟶ 1,183:
[]
(0.00 secs, 0 bytes)
</pre>
A disjointed subsequence is a consecutive subsequence followed by a gap,
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
Line 937 ⟶ 1,194:
(left, _:right) = splitAt n s
main = print $ length $ disjoint [1..20]</
Build a lexicographic list of consecutive subsequences,
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) []
Line 953 ⟶ 1,211:
disjoint s = (subseqs s) `minus` (consecs s)
main = mapM_ print $ disjoint [1..4]</
=={{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 ]
noncont=: <@#~ (#~ firstend < laststart)@allmasks</
Example use:
<
┌───┬───┬───┬─────┬─────┐
│2 4│1 4│1 3│1 3 4│1 2 4│
Line 973 ⟶ 1,231:
└──┴──┴──┴───┴───┴──┴──┴───┴──┴───┴───┴────┴───┴───┴────┴────┘
#noncont i.10
968</
Alternatively, since there are relatively few continuous sequences, we could specifically exclude them:
<
noncont=: <@#~ (allmasks -. contmasks)</
(we get the same behavior from this implementation)
=={{header|Java}}==
<
public static void main(String args[]) {
Line 996 ⟶ 1,256:
}
}
}</
<pre>12 4
Line 1,008 ⟶ 1,268:
{{works with|SpiderMonkey}}
<
var non_continuous = new Array();
for (var i = 0; i < ary.length; i++) {
Line 1,031 ⟶ 1,291:
load('json2.js'); /* http://www.json.org/js.html */
print(JSON.stringify( non_continuous_subsequences( powerset([1,2,3,4]))));</
{{out}}
<pre>[[1,3],[1,4],[2,4],[1,2,4],[1,3,4]]</pre>
Line 1,045 ⟶ 1,305:
subsets, we will use the powerset approach, and accordingly begin by
defining subsets/0 as a generator.
<
def subsets:
if length == 0 then []
Line 1,060 ⟶ 1,320:
def non_continuous_subsequences:
(length | non_continuous_indices) as $ix
| [.[ $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)
</syntaxhighlight>
{{out}}
$ jq -n -f powerset_generator.jq
1048365
=={{header|
This solution uses an iterator over non-contiguous sub-sequences, <tt>NCSubSeq</tt>. In the spirit of Julia's <tt>permutations</tt> and <tt>combinations</tt> built-ins, <tt>NCSubSeq</tt> provides an array of indices that can be used to create each subsequence from the full sequence. Sub-sequences are indexed by integers whose bit patterns indicate which members are included.
<tt>NCSubSeq</tt> works by filtering indices according to whether all <tt>1</tt>s in these indices have bit pattern that are contiguous (using the <tt>iscontseq</tt> functions). This is an easy to implement approach. Greater efficiency might be achieved by exploiting the property that a sequence is contiguous if and only if its index is a difference of two powers of 2. This property is used to create the <tt>length(NCSubSeq(n))</tt> function, which gives the number of non-contiguous sub-sequences of a sequence of length <tt>n</tt>.
<tt>NCSubSeq</tt> works transparently for sequence lengths up to <tt>WORD_SIZE-1</tt> (typically 63). It can be extended to work for longer sequences by casting <tt>n</tt> to a larger integer, e.g. using <tt>Big(n)</tt>. A more polished implementation would handle this extension behind the scenes.
'''Iterator and Functions'''
<syntaxhighlight lang="julia">using Printf, IterTools
import Base.IteratorSize, Base.iterate, Base.length
iscontseq(n::Integer) = count_zeros(n) == leading_zeros(n) + trailing_zeros(n)
iscontseq(n::BigInt) = !ismatch(r"0", rstrip(bin(n), '0'))
function makeint2seq(n::Integer)
idex = collect(1:n)
function int2seq(m::Integer)
d = digits(m, base=2, pad=n)
idex[d .== 1]
end
return int2seq
end
struct NCSubSeq{T<:Integer}
n::T
end
mutable struct NCSubState{T<:Integer}
m::T
m2s::Function
end
Base.IteratorSize(::NCSubSeq) = Base.HasLength()
Base.length(a::NCSubSeq) = 2 ^ a.n - a.n * (a.n + 1) ÷ 2 - 1
function Base.iterate(a::NCSubSeq, as::NCSubState=NCSubState(5, makeint2seq(a.n)))
if 2 ^ a.n - 3 < as.m
return nothing
end
s = as.m2s(as.m)
as.m += 1
while iscontseq(as.m)
as.m += 1
end
return (s, as)
end
n = 4
println("Testing NCSubSeq for ", n, " items:\n ", join(NCSubSeq(n), " "))
s = "Rosetta"
cs = split(s, "")
m = 10
n = length(NCSubSeq(length(cs))) - m
println("\nThe first and last ", m, " NC sub-sequences of \"", s, "\":")
for (i, a) in enumerate(NCSubSeq(length(s)))
i <= m || n < i || continue
println(@sprintf "%6d %s" i join(cs[a], ""))
i == m || continue
println(" .. ......")
end
println("\nThe first and last ", m, " NC sub-sequences of \"", s, "\"")
for x in IterTools.Iterators.flatten([1:10; 20:10:40; big.(50:50:200)])
@printf "%7d → %d\n" x length(NCSubSeq(x))
end
</syntaxhighlight>{{out}}
<pre>
Testing NCSubSeq for 4 items:
[1, 3] [1, 4] [2, 4] [1, 2, 4] [1, 3, 4]
The first and last 10 NC sub-sequences of "Rosetta":
1 Rs
2 Re
3 oe
4 Roe
5 Rse
6 Rt
7 ot
8 Rot
9 st
10 Rst
.. ......
90 otta
91 Rotta
92 stta
93 Rstta
94 ostta
95 Rostta
96 Retta
97 oetta
98 Roetta
99 Rsetta
The first and last 10 NC sub-sequences of "Rosetta"
1 → 0
2 → 0
3 → 1
4 → 5
5 → 16
6 → 42
7 → 99
8 → 219
9 → 466
10 → 968
20 → 1048365
30 → 1073741358
40 → 1099511626955
50 → 1125899906841348
100 → 1267650600228229401496703200325
150 → 1427247692705959881058285969449495136382735298
200 → 1606938044258990275541962092341162602522202993782792835281275
</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.1.2
fun <T> ncs(a: Array<T>) {
fun generate(m: Int, k: Int, c: IntArray) {
if (k == m) {
if (c[m - 1] != c[0] + m - 1) {
for (i in 0 until m) print("${a[c[i]]} ")
println()
}
}
else {
for (j in 0 until a.size) {
if (k == 0 || j > c[k - 1]) {
c[k] = j
generate(m, k + 1, c)
}
}
}
}
for (m in 2 until a.size) {
val c = IntArray(m)
generate(m, 0, c)
}
}
fun main(args: Array<String>) {
val a = arrayOf(1, 2, 3, 4)
ncs(a)
println()
val ca = arrayOf('a', 'b', 'c', 'd', 'e')
ncs(ca)
}</syntaxhighlight>
{{out}}
<pre>
1 3
1 4
2 4
1 2 4
1 3 4
a c
a d
a e
b d
b e
c e
a b d
a b e
a c d
a c e
a d e
b c e
b d e
a b c e
a b d e
a c d e
</pre>
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Non_continuous_subsequences (item$(), display){
Function positions(n) {
function onebit {
=lambda b=false (&c)-> {
=b :if c then b~:c=not b
}
}
dim k(n)=onebit(), p(n)
m=true
flush
for i=1 to 2^n {
for j=0 to n-1 :p(j)= k(j)(&m) :next
m1=p(0)
m2=0
for j=1 to n-1
if m2 then if m1>p(j) then m2=2:exit for
if m1 < p(j) then m2++
m1=p(j)
next
if m2=2 then data cons(p())' push a copy of p() to end of stack
m=true
}
=array([])
}
a=positions(len(item$()))
if display then
For i=0 to len(a)-1
b=array(a,i)
line$=format$("{0::-5})",i+1,)
for j=0 to len(b)-1
if array(b,j) then line$+=" "+item$(j)
next
print line$
doc$<=line$+{
}
next
end if
line$="Non continuous subsequences:"+str$(len(a))
Print line$
doc$<=line$+{
}
}
global doc$
document doc$ ' change string to document object
Non_continuous_subsequences ("1","2","3","4"), true
Non_continuous_subsequences ("a","e","i","o","u"), true
Non_continuous_subsequences ("R","o","s","e","t","t","a"), true
Non_continuous_subsequences ("1","2","3","4","5","6","7","8","9","0"), false
clipboard doc$
</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">
1) 1 3
2) 1 4
3) 2 4
4) 1 2 4
5) 1 3 4
Non continuous subsequences: 5
1) a i
2) a o
3) e o
4) a e o
5) a i o
6) a u
7) e u
8) a e u
9) i u
10) a i u
11) e i u
12) a e i u
13) a o u
14) e o u
15) a e o u
16) a i o u
Non continuous subsequences: 16
1) R s
2) R e
3) o e
4) R o e
5) R s e
6) R t
7) o t
8) R o t
9) s t
10) R s t
11) o s t
12) R o s t
13) R e t
14) o e t
15) R o e t
16) R s e t
17) R t
18) o t
19) R o t
20) s t
21) R s t
22) o s t
23) R o s t
24) e t
25) R e t
26) o e t
27) R o e t
28) s e t
29) R s e t
30) o s e t
31) R o s e t
32) R t t
33) o t t
34) R o t t
35) s t t
36) R s t t
37) o s t t
38) R o s t t
39) R e t t
40) o e t t
41) R o e t t
42) R s e t t
43) R a
44) o a
45) R o a
46) s a
47) R s a
48) o s a
49) R o s a
50) e a
51) R e a
52) o e a
53) R o e a
54) s e a
55) R s e a
56) o s e a
57) R o s e a
58) t a
59) R t a
60) o t a
61) R o t a
62) s t a
63) R s t a
64) o s t a
65) R o s t a
66) e t a
67) R e t a
68) o e t a
69) R o e t a
70) s e t a
71) R s e t a
72) o s e t a
73) R o s e t a
74) R t a
75) o t a
76) R o t a
77) s t a
78) R s t a
79) o s t a
80) R o s t a
81) e t a
82) R e t a
83) o e t a
84) R o e t a
85) s e t a
86) R s e t a
87) o s e t a
88) R o s e t a
89) R t t a
90) o t t a
91) R o t t a
92) s t t a
93) R s t t a
94) o s t t a
95) R o s t t a
96) R e t t a
97) o e t t a
98) R o e t t a
99) R s e t t a
Non continuous subsequences: 99
Non continuous subsequences: 968
</pre >
=={{header|Mathematica}}/{{header|Wolfram Language}}==
We make all the subsets then filter out the continuous ones:
<syntaxhighlight lang="mathematica">GoodBad[i_List]:=Not[MatchQ[Differences[i],{1..}|{}]]
n=5
Select[Subsets[Range[n]],GoodBad]</syntaxhighlight>
{{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>
=={{header|Nim}}==
{{trans|Python}}
<
proc ncsub[T](se: seq[T], s = 0): seq[seq[T]] =
Line 1,091 ⟶ 1,706:
let
x = se[0..0]
xs = se[1 ..
p2 = s mod 2
p1 = (s + 1) mod 2
Line 1,102 ⟶ 1,717:
echo "ncsub(", toSeq 1.. 3, ") = ", ncsub(toSeq 1..3)
echo "ncsub(", toSeq 1.. 4, ") = ", ncsub(toSeq 1..4)
echo "ncsub(", toSeq 1.. 5, ") = ", ncsub(toSeq 1..5)</
{{out}}
<pre>ncsub(@[1, 2, 3]) = @[@[1, 3]]
ncsub(@[1, 2, 3, 4]) = @[@[1, 2, 4], @[1, 3, 4], @[1, 3], @[1, 4], @[2, 4]]
Line 1,112 ⟶ 1,727:
{{trans|Generalized monadic filter}}
<
[] ->
if s >= 3 then
Line 1,133 ⟶ 1,748:
fence (s + 1) xs
let ncsubseq = fence 0</
{{out}}
<pre># ncsubseq [1;2;3];;
- : int list list = [[1; 3]]
Line 1,149 ⟶ 1,763:
=={{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}
Line 1,173 ⟶ 1,787:
end
in
{Inspect {NCSubseq [1 2 3 4]}}</
=={{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,
Line 1,186 ⟶ 1,800:
};
nonContigSubseq([1,2,3])
nonContigSubseq(["a","b","c","d","e"])</
{{out}}
<pre>[1, 3]
Line 1,208 ⟶ 1,822:
=={{header|Perl}}==
<
sub non_continuous {
my ($idx, $has_gap
my $found;
for ($idx .. $max) {
Line 1,223 ⟶ 1,838:
}
$max = 20;
print "found ", non_continuous(1), " sequences\n";</
{{out}}
<pre>found 1048365 sequences</pre>
=={{header|
Straightforward recursive implementation, the only minor trick is that a gap does not
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
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #008080;">procedure</span> <span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">rest</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">contig</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">>=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">contig</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">taken</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">ri</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">contig</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{})</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span>
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{})</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">ncs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{1,3}
"==="
{1,2,4}
{1,3,4}
{1,3}
{1,4}
{2,4}
"==="
"0.3s"
{0,0,1,5,16,42,99,219,466,968,1981,4017,8100,16278,32647,65399,130918,261972,524097,1048365}
</pre>
=={{header|Picat}}==
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 =>
println(1..4=non_cont(1..4)),
L = "abcde".reverse(),
println(L=non_cont(L)),
println(ernit=non_cont("ernit")),
println(aaa=non_cont("aaa")),
println(aeiou=non_cont("aeiou")),
nl,
println("Printing just the lengths for 1..N for N = 1..20:"),
foreach(N in 1..20)
println(1..N=non_cont(1..N).length) % just the length
end,
nl.
% get all the non-continuous subsequences
non_cont(L) = [ [L[I] : I in S] : S in non_cont_ixs(L.length)].
% 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].</syntaxhighlight>
{{out}}
<pre>[1,2,3,4] = [[2,4],[1,4],[1,3],[1,3,4],[1,2,4]]
edcba = [ca,da,db,dba,dca,ea,eb,eba,ec,eca,ecb,ecba,eda,edb,edba,edca]
ernit = [nt,rt,ri,rit,rnt,et,ei,eit,en,ent,eni,enit,ert,eri,erit,ernt]
aaa = [aa]
aeiou = [iu,eu,eo,eou,eiu,au,ao,aou,ai,aiu,aio,aiou,aeu,aeo,aeou,aeiu]
Printing just the lengths for 1..N for N = 1..20:
[1] = 0
[1,2] = 0
[1,
[1,2,3,4,5] = 16
[1,2,3,4,5,6] = 42
[1,2,3,4,5,6,7] = 99
[1,2,3,4,5,6,7,8] = 219
[1,2,3,4,5,6,7,8,9] = 466
[1,2,3,4,5,6,7,8,9,10] = 968
[1,2,3,4,5,6,7,8,9,10,11] = 1981
[1,2,3,4,5,6,7,8,9,10,11,12] = 4017
[1,2,3,4,5,6,7,8,9,10,11,12,13] = 8100
[1,2,3,4,5,6,7,8,9,10,11,12,13,14] = 16278
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] = 32647
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] = 65399
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17] = 130918
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] = 261972
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] = 524097
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] = 1048365</pre>
=={{header|PicoLisp}}==
{{trans|Scheme}}
<
(let S 0
(recur (S Lst)
Line 1,259 ⟶ 1,966:
(mapcar '((YS) (cons X YS))
(recurse S XS) )
(recurse (inc S) XS) ) ) ) ) ) ) )</
=={{header|Pop11}}==
Line 1,266 ⟶ 1,973:
variables to keep track if subsequence is continuous.
<
lvars acc = [], gap_started = false, is_continuous = true;
define do_it(l1, l2);
Line 1,289 ⟶ 1,996:
enddefine;
ncsubseq([1 2 3 4 5]) =></
{{out}}
<
[2 3 5] [1 2 3 5] [1 4 5] [2 4 5] [1 2 4 5] [1 3 4 5]]</
=={{header|PowerShell}}==
<
{
$sc = $S.count
Line 1,364 ⟶ 2,071:
}
( NonContinuous-SubSequence 'a','b','c','d','e' ) | Select-Object length, @{Name='value';Expression={ $_ } } | Sort-Object length, value | ForEach-Object { $_.value }</
=={{header|Prolog}}==
Line 1,370 ⟶ 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.
<syntaxhighlight lang="prolog">
% fetch all the subsequences
ncsubs(L, LNCSL) :-
Line 1,396 ⟶ 2,103:
reverse(L, [_|SL1]),
reverse(SL1, SL)).
</syntaxhighlight>
Example :
<
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]]</
=={{header|Python}}==
{{trans|Scheme}}
<
if seq:
x = seq[:1]
Line 1,412 ⟶ 2,119:
return [x + ys for ys in ncsub(xs, s + p1)] + ncsub(xs, s + p2)
else:
return [[]] if s >= 3 else []</
{{out}}
<pre>>>> ncsub(range(1, 4))
[[1, 3]]
Line 1,427 ⟶ 2,133:
A faster Python + Psyco JIT version:
<
import psyco
Line 1,466 ⟶ 2,172:
psyco.full()
n = 10 if len(argv) < 2 else int(argv[1])
print len( ncsub(range(1, n)) )</
=={{header|Quackery}}==
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
[ dup 0 != while
2/mod iff
[ dip 1+ ] done
again ]
[ dup 0 != while
2/mod not iff
[ dip 1+ ] done
again ]
[ dup 0 != while
2/mod iff
[ dip 1+ ] done
again ]
drop 3 = ] is noncontinuous ( n --> b )
[ [] unrot
[ dup 0 != while
dip behead tuck
1 & iff
[ nested dip rot
join unrot ]
else drop
1 >> again ]
2drop ] is bitems ( [ n --> [ )
[ [] swap
dup size bit times
[ i^ noncontinuous if
[ dup i^ bitems
nested rot
join swap ] ]
drop ] is ncsubs ( [ --> [ )
' [ 1 2 3 4 ] ncsubs echo cr
$ "quackery" ncsubs 72 wrap$</syntaxhighlight>
{{out}}
<pre>[ [ 1 3 4 ] [ 1 2 4 ] [ 2 4 ] [ 1 4 ] [ 1 3 ] ]
qackery quckery uckery qckery quakery uakery qakery akery qukery ukery
qkery quacery uacery qacery acery qucery ucery qcery cery quaery uaery
qaery aery query uery qery quackry uackry qackry ackry quckry uckry
qckry ckry quakry uakry qakry akry qukry ukry qkry kry quacry uacry
qacry acry qucry ucry qcry cry quary uary qary ary qury ury qry quackey
uackey qackey ackey quckey uckey qckey ckey quakey uakey qakey akey
qukey ukey qkey key quacey uacey qacey acey qucey ucey qcey cey quaey
uaey qaey aey quey uey qey ey quacky uacky qacky acky qucky ucky qcky
cky quaky uaky qaky aky quky uky qky ky quacy uacy qacy acy qucy ucy qcy
cy quay uay qay ay quy uy qy qacker qucker ucker qcker quaker uaker
qaker aker quker uker qker quacer uacer qacer acer qucer ucer qcer cer
quaer uaer qaer aer quer uer qer quackr uackr qackr ackr quckr uckr qckr
ckr quakr uakr qakr akr qukr ukr qkr kr quacr uacr qacr acr qucr ucr qcr
cr quar uar qar ar qur ur qr qacke qucke ucke qcke quake uake qake ake
quke uke qke quace uace qace ace quce uce qce ce quae uae qae ae que ue
qe qack quck uck qck quak uak qak ak quk uk qk qac quc uc qc qa
</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.
<
{
n <- length(x)
Line 1,487 ⟶ 2,258:
# Example usage
ncsub(1:4)
ncsub(letters[1:5])</
=={{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)))))
</syntaxhighlight>
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)
Line 1,512 ⟶ 2,283:
(non-continuous-subseqs '(1 2 3 4))
;; => '((1 2 4) (1 3 4) (1 3) (1 4) (2 4))
</syntaxhighlight>
=={{header|
(formerly Perl 6)
{{works with|rakudo|2015-09-24}}
<syntaxhighlight lang="raku" line>sub non_continuous_subsequences ( *@list ) {
@list.combinations.grep: { 1 != all( .[ 0 ^.. .end] Z- .[0 ..^ .end] ) }
}
say non_continuous_subsequences( 1..3 )».gist;
say non_continuous_subsequences( 1..4 )».gist;
say non_continuous_subsequences( ^4 ).map: {[<a b c d>[.list]].gist};</syntaxhighlight>
{{out}}
<pre>((1 3))
((1 3) (1 4) (2 4) (1 2 4) (1 3 4))
([a c] [a d] [b d] [a b d] [a c d])</pre>
=={{header|REXX}}==
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
if list='' | list=="," then
say 'list=' space(list); say /*display the list to the terminal. */
w= words(list) /*W: is the number of items in list. */
nums= strip( left(123456789, w) ) /*build a string of decimal digits. */
tail= right(nums, max(0, w-2) ) /*construct a fast tail for comparisons*/
#= 0 /*#: number of non─continuous subseq. */
do j=13 to left(nums,1) || tail /*step through list (using smart start)*/
if verify(j, nums) \== 0 then iterate /*Not one of the chosen (sequences) ? */
f= left(j, 1) /*use the fist decimal digit of J. */
NCS= 0 /*so far, no non─continuous subsequence*/
do k=2 for length(j)-1 /*search for " " " */
x= substr(j, k, 1) /*extract a single decimal digit of J.*/
if x <= f then iterate j /*if next digit ≤, then skip this digit*/
if x \== f+1 then NCS= 1 /*it's OK as of now (that is, so far).*/
f= x /*now have a new next decimal digit. */
end /*k*/
$=
if \NCS then iterate /*not OK? Then skip this number (item)*/
#= # + 1 /*Eureka! We found a number (or item).*/
do m=1 for length(j) /*build a sequence string to display. */
$= $ word(list, substr(j, m, 1) ) /*obtain a number (or item) to display.*/
end /*m*/
say 'a
end /*j*/
say /*help ensure visual fidelity in output*/
if #==0 then #= 'no' /*make it look more gooder
say
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
s: if arg(1)==1 then return ''; return word( arg(2) 's', 1) /*
<pre>
list= 1 2 3 4
Line 1,560 ⟶ 2,347:
5 non-continuous subsequences were found.
</pre>
<pre>
list= a e I o u
Line 1,583 ⟶ 2,370:
16 non-continuous subsequences were found.
</pre>
<pre>
list= Alderney Guernsey Herm Jersey Sark
Line 1,606 ⟶ 2,393:
16 non-continuous subsequences were found.
</pre>
<pre>
list= helium neon argon krypton xenon radon
Line 1,654 ⟶ 2,441:
42 non-continuous subsequences were found.
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Non-continuous subsequences
load "stdlib.ring"
list = [1,2,3,4]
items = newlist(pow(2,len(list))-1,len(list))
see "For [1, 2, 3, 4] non-continuous subsequences are:" + nl
powerset(list,4)
showarray(items,4)
see nl
list = [1,2,3,4,5]
items = newlist(pow(2,len(list))-1,len(list))
see "For [1, 2, 3, 4, 5] non-continuous subsequences are:" + nl
powerset(list,5)
showarray(items,5)
func showarray(items,ind)
for n = 1 to len(items)
flag = 0
for m = 1 to ind - 1
if items[n][m] = 0 or items[n][m+1] = 0
exit
ok
if (items[n][m] + 1) != items[n][m+1]
flag = 1
exit
ok
next
if flag = 1
see "["
str = ""
for x = 1 to len(items[n])
if items[n][x] != 0
str = str + items[n][x] + " "
ok
next
str = left(str, len(str) - 1)
see str + "]" + nl
ok
next
func powerset(list,ind)
num = 0
num2 = 0
items = newlist(pow(2,len(list))-1,ind)
for i = 2 to (2 << len(list)) - 1 step 2
num2 = 0
num = num + 1
for j = 1 to len(list)
if i & (1 << j)
num2 = num2 + 1
if list[j] != 0
items[num][num2] = list[j]
ok
ok
next
next
return items
</syntaxhighlight>
Output:
<pre>
For [1, 2, 3, 4] non-continuous subsequences are:
[1 3]
[1 4]
[2 4]
[1 2 4]
[1 3 4]
For [1, 2, 3, 4, 5] non-continuous subsequences are:
[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>
Line 1,661 ⟶ 2,537:
Uses code from [[Power Set]].
<
def func_power_set
inject([[]]) { |ps,item| # for each item in the Array
Line 1,682 ⟶ 2,558:
p (1..4).to_a.non_continuous_subsequences
p (1..5).to_a.non_continuous_subsequences
p ("a".."d").to_a.non_continuous_subsequences</
{{out}}
Line 1,692 ⟶ 2,568:
</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)}
Line 1,699 ⟶ 2,575:
end
p %w(a e i o u).non_continuous_subsequences</
{{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>
=={{header|
<syntaxhighlight lang="scala">object NonContinuousSubSequences extends App {
private def seqR(s: String, c: String, i: Int, added: Int): Unit = {
if (i == s.length) {
if (c.trim.length > added) println(c)
} else {
seqR(s, c + s(i), i + 1, added + 1)
seqR(s, c + " ", i + 1, added)
}
}
seqR("1234", "", 0, 0)
}</syntaxhighlight>
=={{header|Scheme}}==
{{trans|Generalized monadic filter}}
<syntaxhighlight lang="scheme">(define (ncsubseq lst)
(let recurse ((s 0)
(lst lst))
Line 1,725 ⟶ 2,614:
(map (lambda (ys) (cons x ys))
(recurse s xs))
(recurse (+ s 1) xs)))))))</
{{out}}
<pre>> (ncsubseq '(1 2 3))
((1 3))
Line 1,737 ⟶ 2,625:
=={{header|Seed7}}==
<
const func array bitset: ncsub (in bitset: seq, in integer: s) is func
Line 1,766 ⟶ 2,654:
writeln(seq);
end for;
end func;</
{{out}}
Line 1,775 ⟶ 2,663:
{1, 4}
{2, 4}
</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">func non_continuous(min, max, subseq=[], has_gap=false) {
static current = [];
range(min, max).each { |i|
current.push(i);
has_gap && subseq.append([current...]);
i < max && non_continuous(i.inc, max, subseq, has_gap);
current.pop;
has_gap = current.len;
}
subseq;
}
say non_continuous(1, 3);
say non_continuous(1, 4);
say non_continuous("a", "d");</syntaxhighlight>
{{out}}
<pre>
[[1, 3]]
[[1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2, 4]]
[["a", "b", "d"], ["a", "c"], ["a", "c", "d"], ["a", "d"], ["b", "d"]]
</pre>
Line 1,781 ⟶ 2,696:
{{trans|Generalized monadic filter}}
<
if s >= 3 then
[[]]
Line 1,801 ⟶ 2,716:
fence (s + 1) xs
fun ncsubseq xs = fence 0 xs</
{{out}}
<pre>- ncsubseq [1,2,3];
val it = [[1,3]] : int list list
Line 1,817 ⟶ 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'':
<
set res [list [list]]
foreach e $l {
Line 1,839 ⟶ 2,753:
% lfilter is_not_continuous [subsets {1 2 3 4}]
{1 3} {1 4} {2 4} {1 2 4} {1 3 4}</
=={{header|Ursala}}==
Line 1,845 ⟶ 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).
<
noncontinuous = num; ^rlK3ZK17rSS/~& powerset
Line 1,851 ⟶ 2,765:
#show+
examples = noncontinuous 'abcde'</
{{out}}
<pre>abce
abd
Line 1,871 ⟶ 2,784:
be
ce</pre>
=={{header|VBScript}}==
{{trans|BBC BASIC}}
<syntaxhighlight lang="vb">'Non-continuous subsequences - VBScript - 03/02/2021
Function noncontsubseq(l)
Dim i, j, g, n, r, s, w, m
Dim a, b, c
n = Ubound(l)
For s = 0 To n-2
For g = s+1 To n-1
a = "["
For i = s To g-1
a = a & l(i) & ", "
Next 'i
For w = 1 To n-g
r = n+1-g-w
For i = 1 To 2^r-1 Step 2
b = a
For j = 0 To r-1
If i And 2^j Then b=b & l(g+w+j) & ", "
Next 'j
c = (Left(b, Len(b)-1))
WScript.Echo Left(c, Len(c)-1) & "]"
m = m+1
Next 'i
Next 'w
Next 'g
Next 's
noncontsubseq = m
End Function 'noncontsubseq
list = Array("1", "2", "3", "4")
WScript.Echo "List: [" & Join(list, ", ") & "]"
nn = noncontsubseq(list)
WScript.Echo nn & " non-continuous subsequences" </syntaxhighlight>
{{out}}
<pre>
List: [1, 2, 3, 4]
[1, 3]
[1, 3, 4]
[1, 4]
[1, 2, 4]
[2, 4]
5 non-continuous subsequences
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
Needed a bit of doctoring to do the character example as Wren only has strings.
<syntaxhighlight lang="wren">import "./fmt" for Fmt
var ncs = Fn.new { |a|
var f = "$d "
if (a[0] is String) {
for (i in 0...a.count) a[i] = a[i].bytes[0]
f = "$c "
}
var generate // recursive
generate = Fn.new { |m, k, c|
if (k == m) {
if (c[m - 1] != c[0] + m - 1) {
for (i in 0...m) Fmt.write(f, a[c[i]])
System.print()
}
} else {
for (j in 0...a.count) {
if (k == 0 || j > c[k - 1]) {
c[k] = j
generate.call(m, k + 1, c)
}
}
}
}
for (m in 2...a.count) {
var c = List.filled(m, 0)
generate.call(m, 0, c)
}
}
var a = [1, 2, 3, 4]
ncs.call(a)
System.print()
var ca = ["a", "b", "c", "d", "e"]
ncs.call(ca)</syntaxhighlight>
{{out}}
<pre>
1 3
1 4
2 4
1 2 4
1 3 4
a c
a d
a e
b d
b e
c e
a b d
a b e
a c d
a c e
a d e
b c e
b d e
a b c e
a b d e
a c d e
</pre>
=={{header|XPL0}}==
{{trans|Wren}}
<syntaxhighlight lang "XPL0">proc NCS(A, Size, Char);
int A, Size, Char;
int C, M;
proc Generate(M, K, C); \recursive
int M, K, C;
int I, J;
[if K = M then
[if C(M-1) # C(0)+M-1 then
[for I:= 0 to M-1 do
[if Char then ChOut(0, A(C(I)))
else IntOut(0, A(C(I)));
ChOut(0, ^ );
];
CrLf(0);
];
]
else
[for J:= 0 to Size-1 do
[if K = 0 or J > C(K-1) then
[C(K):= J;
Generate(M, K+1, C);
];
];
];
];
[C:= Reserve(Size*4);
for M:= 2 to Size-1 do Generate(M, 0, C);
];
int A, CA;
[A:= [1, 2, 3, 4];
NCS(A, 4, false);
CrLf(0);
CA:= [^a, ^b, ^c, ^d, ^e];
NCS(CA, 5, true);
]</syntaxhighlight>
{{out}}
<pre>
1 3
1 4
2 4
1 2 4
1 3 4
a c
a d
a e
b d
b e
c e
a b d
a b e
a c d
a c e
a d e
b c e
b d e
a b c e
a b d e
a c d e
</pre>
=={{header|zkl}}==
{{trans|JavaScript}}
<
pwerSet(ary).filter(fcn(list){(not isContinuous(list)) })
}
Line 1,882 ⟶ 2,974:
return(True);
}
non_continuous_subsequences(T(1,2,3,4)).println();</
<syntaxhighlight lang="zkl">fcn pwerSet(list){
(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)) })
}
brokenSubsequences("1234").println();</
{{out}}
<pre>
|