Comment #0 by bearophile_hugs — 2014-07-04T08:52:40Z
I suggest to add to Phobos a combinations() range with this API (std.range.combinations sounds better, but cartesianProduct is in std.algorithm, so I think this function should be std.algorithm.combinations):
module combinations3;
import std.traits: Unqual;
struct Combinations(T, bool copy=true) {
Unqual!T[] pool, front;
size_t r, n;
bool empty = false;
size_t[] indices;
size_t len;
bool lenComputed = false;
this(T[] pool_, in size_t r_) pure nothrow @safe {
this.pool = pool_.dup;
this.r = r_;
this.n = pool.length;
if (r > n)
empty = true;
indices.length = r;
foreach (immutable i, ref ini; indices)
ini = i;
front.length = r;
foreach (immutable i, immutable idx; indices)
front[i] = pool[idx];
}
@property size_t length() /*logic_const*/ pure nothrow @nogc {
static size_t binomial(size_t n, size_t k) pure nothrow @safe @nogc
in {
assert(n > 0, "binomial: n must be > 0.");
} body {
if (k < 0 || k > n)
return 0;
if (k > (n / 2))
k = n - k;
size_t result = 1;
foreach (size_t d; 1 .. k + 1) {
result *= n;
n--;
result /= d;
}
return result;
}
if (!lenComputed) {
// Set cache.
len = binomial(n, r);
lenComputed = true;
}
return len;
}
void popFront() pure nothrow @safe {
if (!empty) {
bool broken = false;
size_t pos = 0;
foreach_reverse (immutable i; 0 .. r) {
pos = i;
if (indices[i] != i + n - r) {
broken = true;
break;
}
}
if (!broken) {
empty = true;
return;
}
indices[pos]++;
foreach (immutable j; pos + 1 .. r)
indices[j] = indices[j - 1] + 1;
static if (copy)
front = new Unqual!T[front.length];
foreach (immutable i, immutable idx; indices)
front[i] = pool[idx];
}
}
}
// Helper.
Combinations!(T, copy) combinations(bool copy=true, T)
(T[] items, in size_t k)
in {
assert(items.length, "combinations: items can't be empty.");
} body {
return typeof(return)(items, k);
}
void main() {
import std.stdio, std.array, std.algorithm;
[1, 2, 3, 4].combinations!false(2).array.writeln;
[1, 2, 3, 4].combinations!true(2).array.writeln;
[1, 2, 3, 4].combinations(2).map!(x => x).writeln;
}
The "copy" bool template argument is on default true, and it means every result is a copy, for safety and correctness. When you know what you are doing you can set it to false, to speed up.
Comment #1 by bearophile_hugs — 2014-07-04T11:38:23Z
import std.traits: Unqual;
size_t binomial(size_t n, size_t k) pure nothrow @safe @nogc
in {
assert(n > 0, "binomial: n must be > 0.");
} body {
if (k < 0 || k > n)
return 0;
if (k > (n / 2))
k = n - k;
size_t result = 1;
foreach (size_t d; 1 .. k + 1) {
result *= n;
n--;
result /= d;
}
return result;
}
struct CombinationsFixed(size_t k, T) {
Unqual!T[k] front;
Unqual!T[] pool;
size_t n;
bool empty = false;
size_t[k] indices;
size_t len;
bool lenComputed = false;
this(T[] pool_) pure nothrow @safe {
this.pool = pool_.dup; // Can't be @nogc.
this.n = pool.length;
if (k > n)
empty = true;
foreach (immutable i, ref ini; indices)
ini = i;
foreach (immutable i, immutable idx; indices)
front[i] = pool[idx];
}
@property size_t length() /*logic_const*/ pure nothrow @nogc {
if (!lenComputed) {
// Set cache.
len = binomial(n, k);
lenComputed = true;
}
return len;
}
void popFront() pure nothrow @safe @nogc {
if (!empty) {
bool broken = false;
size_t pos = 0;
foreach_reverse (immutable i; 0 .. k) {
pos = i;
if (indices[i] != i + n - k) {
broken = true;
break;
}
}
if (!broken) {
empty = true;
return;
}
indices[pos]++;
foreach (immutable j; pos + 1 .. k)
indices[j] = indices[j - 1] + 1;
foreach (immutable i, immutable idx; indices)
front[i] = pool[idx];
}
}
}
CombinationsFixed!(k, T) combinationsFixed(size_t k, T)
(T[] items)
in {
assert(items.length, "combinations: items can't be empty.");
} body {
return typeof(return)(items);
}
void main() {
import std.stdio, std.array, std.algorithm;
[1, 2, 3, 4].combinationsFixed!2.map!(x => x).writeln;
[1, 2, 3, 4].combinationsFixed!2.array.writeln;
}