[Issue 13596] New: permutations range

[via Digitalmars-d-bugs]

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

          Issue ID: 13596
           Summary: permutations range
           Product: D
           Version: D2
          Hardware: x86
                OS: Windows
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: Phobos
          Assignee: nobody at puremagic.com
          Reporter: bearophile_hugs at eml.cc

std.algorithm.nextPermutation is useful, but most times I prefer to compute
permutations in functional-style UFCS chains istead of do-while loops.

So I suggest to add a range similar to this to Phobos (to std.algorithm or
std.range):

- - - - - - - - - - - - - - - - - -

import std.algorithm, std.conv, std.traits;

struct Permutations(bool doCopy=true, T) if (isMutable!T) {
    private immutable size_t num;
    private T[] items;
    private uint[31] indexes;
    private ulong tot;

    this (in T[] items) pure nothrow @safe
    in {
        static enum string L = indexes.length.text;
        assert(items.length >= 0 && items.length <= indexes.length,
               "Permutations: items.length must be >= 0 && < " ~ L);
    } body {
        static ulong factorial(in size_t n) pure nothrow @safe {
            ulong result = 1;
            foreach (immutable i; 2 .. n + 1)
                result *= i;
            return result;
        }

        this.num = items.length;
        this.items = items.dup;
        foreach (immutable i; 0 .. cast(typeof(indexes[0]))this.num)
            this.indexes[i] = i;
        this.tot = factorial(this.num);
    }

    @property T[] front() pure nothrow @safe {
        static if (doCopy) {
            return items.dup;
        } else
            return items;
    }

    @property bool empty() const pure nothrow @safe @nogc {
        return tot == 0;
    }

    @property size_t length() const pure nothrow @safe @nogc {
        // Not cached to keep the function pure.
        typeof(return) result = 1;
        foreach (immutable x; 1 .. items.length + 1)
            result *= x;
        return result;
    }

    void popFront() pure nothrow {
        tot--;
        if (tot > 0) {
            size_t j = num - 2;

            while (indexes[j] > indexes[j + 1])
                j--;
            size_t k = num - 1;
            while (indexes[j] > indexes[k])
                k--;
            swap(indexes[k], indexes[j]);
            swap(items[k], items[j]);

            size_t r = num - 1;
            size_t s = j + 1;
            while (r > s) {
                swap(indexes[s], indexes[r]);
                swap(items[s], items[r]);
                r--;
                s++;
            }
        }
    }
}

Permutations!(doCopy,T) permutations(bool doCopy=true, T)
                                    (in T[] items)
pure nothrow if (isMutable!T) {
    return Permutations!(doCopy, T)(items);
}

void main() {
    import std.stdio, std.bigint;
    alias B = BigInt;
    foreach (p; [B(1), B(2), B(3)].permutations)
        assert((p[0] + 1) > 0);
    [1, 2, 3].permutations!false.writeln;
    [B(1), B(2), B(3)].permutations!false.writeln;
}

- - - - - - - - - - - - - - - - - -

I'd also like a similar range for combinations. Such lazy iterables are used
all the time in Python programs:


>>> from itertools import permutations, combinations
>>> a = [1, 2, 3, 4]
>>> permutations(a)
<itertools.permutations object at 0x01977030>
>>> list(permutations(a))
[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4,
3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3),
(2, 4
, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2),
(3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1,
2
), (4, 3, 2, 1)]
>>> combinations(a, 2)
<itertools.combinations object at 0x01977030>
>>> list(combinations(a, 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]



I have used this range many times, and I've seen that often the length of the
sequence to permute is a compile-time constant. So in many cases I'd like to
not lose this compile-time information (see also Issue 13594 ). I have also
seen that often I need a range of tuples instead of arrays. Such problems can
be solved with a map!() that follows the permutations range call:


void main() {
    import std.stdio, std.bigint;

    [1, 2, 3, 4]
    .permutations
    .map!(a => tuple(a[0], a[1], a[2], a[3]))
    .writeln;

    [1, 2, 3, 4]
    .permutations
    .map!((a) { int[4] b = a[]; return b; })
    .writeln;    
}



But that's not nice. So perhaps it's a good idea to optionally specify the
output type (this is similar to the zip enhancement idea of Issue 8715 ):


void main() {
    import std.stdio, std.bigint;

    [1, 2, 3, 4]
    .permutations!(true, Tuple!(int, int, int, int))
    .writeln;

    [1, 2, 3, 4]
    .permutations!(true, int[4])
    .writeln;    
}


Note: in such cases you can't specify a false doCopy, because the output items
are values:

.permutations!(false, int[4]) // error

--