Rosetta Code

Non-continuous subsequences: Difference between revisions

Page Discussion

Non-continuous subsequences (view source)

Revision as of 21:48, 6 August 2008

490 bytes removed ,  15 years ago
→‎{{header|D}}
Line 15:
=={{header|D}}==
 
A short version adapted from the Python code:
The list of non-continuous subsequences is constructed in the following way:
# Select some continuous subsequences of length at least 3 from the original sequence;
# From each such continuous subsequences, remove arbitrary elements from the middle, but always keep the first and last element.
 
That cannot generate duplicate sequences, because first and last elements determine the corresponding continous sequence uniquely. Also, sequences of length less than three cannot contain non-continuous subsequences by definition.
 
<d>module ncsub ;
import std.stdio ;
 
struct Combi {
private int n_, m_ ;
alias int delegate(inout int[]) dg_type ;
int opApply(dg_type dg) { return combinate([], 0, m_, dg) ; }
int combinate(int[] fixed, int next, int left, dg_type dg) {
if (left <= 0) dg(fixed) ;
else
for(int i = next ; i < n_ - left + 1; i++)
combinate(fixed ~ [i+1], i + 1, left - 1, dg) ;
return 0 ;
}
}
 
T[] takesome(T)(T[] seq, int[] rmIndexs) {
T[] res = seq.dup ;
foreach(idx ; rmIndexs.reverse)
res = res[0..idx] ~ res[idx+1..$] ;
return res ;
}
 
T[][] ncsub(T)(T[] seq) {
if(seq.length < 3) return [] ;
T[][] ncset ;
for(int head = 0 ; head < seq.length - 2 ; head++)
for(int tail = head + 2 ; tail < seq.length ; tail++) {
T[] contseq = seq[head..tail+1] ;
for(int takeNum = 1 ; takeNum < contseq.length - 1 ; takeNum++)
foreach(removeIndexs ; Combi(contseq.length - 2, takeNum))
ncset ~= takesome(contseq, removeIndexs) ;
}
return ncset ;
}
 
void main() {
writefln(ncsub([1,2,3])) ;
writefln(ncsub([1,2,3,4])) ;
writefln(ncsub([1,2,3,4,5])) ; // results match Haskell examples
writefln(ncsub([1,1,1,1,1])) ;
}</d>
 
Shorter and faster alternative version, adapted from the Python version:
 
<d>
Line 93 ⟶ 44:
[1,4,5],[1,4],[1,5],[2,3,5],[2,4,5],[2,4],[2,5],[3,5]]
</pre>
 
A fast lazy version, it doesn't copy the generated sub-arrays, so if you want to keep them you have to copy (dup) them:
 
<d>
import std.conv: toInt;
import std.stdio: writefln;
 
struct Ncsub(T) {
T[] seq;
 
int opApply(int delegate(ref int[]) dg) {
int result, n = seq.length;
auto S = new int[n];
 
OUTER:
for (int i = 1; i < (1 << seq.length); i++) {
int len_S;
bool nc = false;
for (int j; j < seq.length + 1; j++) {
int k = i >> j;
if (k == 0) {
if (nc) {
T[] auxS = S[0 .. len_S];
result = dg(auxS);
if (result)
break OUTER;
}
break;
} else if (k % 2)
S[len_S++] = seq[j];
else if (len_S)
nc = true;
}
}
 
return result;
}
}
 
void main(string[] args) {
int n = args.length == 2 ? toInt(args[1]) : 10;
 
auto range = new int[n - 1];
foreach (i, ref el; range)
el = i + 1;
 
int count;
foreach (sub; Ncsub!(int)(range))
count++;
writefln(count);
}
</d>
 
=={{header|Haskell}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/65275"