Comment #0 by bearophile_hugs — 2014-10-10T11:43:21Z
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
Comment #1 by dlang-bugzilla — 2015-07-10T07:20:23Z
Comment #4 by bearophile_hugs — 2015-07-18T11:47:16Z
(In reply to bearophile_hugs from comment #3)
> (In reply to github-bugzilla from comment #2)
> > Commit pushed to master at https://github.com/D-Programming-Language/phobos
> >
> > https://github.com/D-Programming-Language/phobos/commit/
> > 6079e23d827ffeaf15b6587eb713fa95a20e4e6f
> > std.algorithm.iteration: Add permutations (fix issue 13596)
>
> You have missed the "doCopy" compilation argument, that gives safety.
You can also add an optional runtime argument, to supply the array of indexes, to make everything @nogc if desired.
Comment #5 by github-bugzilla — 2015-10-04T18:19:57Z