Anonymous user
Non-continuous subsequences: Difference between revisions
Updated D versions 1 and 2 + added third version
m ({{out}}) |
(Updated D versions 1 and 2 + added third version) |
||
Line 697:
===Recursive Version===
{{trans|Python}}
<lang d>import std.stdio;▼
▲T[][] ncsub(T)(in T[] seq, in int s=0) pure nothrow {
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 {
[1, 2, 3,
foreach (const nc; [1, 2, 3, 4, 5].ncsub)
}</lang>
{{out}}
Line 734:
[2, 5]
[3, 5]</pre>
===Faster Lazy Version===
This version doesn't copy the sub-arrays.
Line 739 ⟶ 740:
T[] seq;
int opApply(int delegate(ref
immutable
int result;
auto S = new
OUTER: foreach (immutable i; 1 .. 1 << n) {
▲ FOR_I:
int len_S;▼
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:
void main() {
import std.array, std.range;
//assert
uint counter = 0;
foreach (s; Ncsub!int(r))
counter++;
assert(counter == 16_776_915);
}</lang>
===Generator Version===
This version doesn't copy the sub-arrays, and it's a little slower than the opApply-based version.
<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;
}</lang>
| |||