[Issue 13039] combinations

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13039

Seb  changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 Resolution|--- |DUPLICATE

--- Comment #3 from Seb  ---


*** This issue has been marked as a duplicate of issue 6788 ***

--

[Issue 13039] combinations

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13039

Seb  changed:

   What|Removed |Added

 CC||greensunn...@gmail.com

--- Comment #2 from Seb  ---
See also: https://github.com/dlang/phobos/pull/4026

It has been reworked to mir.combinatorics and works in @nogc:
http://docs.mir.dlang.io/latest/mir_combinatorics.html

--

[Issue 13039] combinations

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13039

Vladimir Panteleev  changed:

   What|Removed |Added

   Keywords||patch

--

[Issue 13039] combinations

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13039

--- Comment #1 from bearophile_h...@eml.cc ---
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;
}

--