[Issue 13039] combinations

[via Digitalmars-d-bugs]

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

--- Comment #1 from bearophile_hugs at 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;
}

--