Recently "quickfur" and Andrei have added C++-style functions
(nextPermutation and nextEvenPermutation) to std.algorithm to
perform permutations, this is a Phobos improvement and I've
already used them few times:
https://github.com/D-Programming-Language/phobos/compare/857f1ed87593...61d26e7dcf2f
Such functions take in account duplications (this is useful), and
require the items to be comparable.
But in many cases I have a set of items, and I want to find (most
or all of) their permutations lazily (even if they are not
comparable). In many of such cases I prefer a permutations
generator that plays well with ranges:
auto result = items
.permutations()
.filter!pred()
.map!foo();
I have other cases in both Python and D where having a lazy
permutations (or combinations) generator/range is handy.
A simple version of such range:
http://rosettacode.org/wiki/Permutations#Fast_Lazy_Version
- - - - - - - - - - - - -
A simple speed benchmark seems to show that a permutations Range
is not bad (0.90 seconds for the range versus 2.76 seconds for
nextPermutation to fully permute 11 integers):
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*/
in {
static enum string L = text(indexes.length); // impure
assert(items.length >= 0 && items.length <=
indexes.length,
"Permutations: items.length must be >= 0 && < " ~
L);
} body {
static ulong factorial(in uint n) pure nothrow {
ulong result = 1;
foreach (i; 2 .. n + 1)
result *= i;
return result;
}
this.num = items.length;
this.items = items.dup;
foreach (i; 0 .. cast(typeof(indexes[0]))this.num)
this.indexes[i] = i;
this.tot = factorial(this.num);
}
@property T[] front() pure nothrow {
static if (doCopy) {
//return items.dup; // Not nothrow.
auto items2 = new T[items.length];
items2[] = items;
return items2;
} else
return items;
}
@property bool empty() const pure nothrow {
return tot == 0;
}
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)
(T[] items)
if (isMutable!T) {
return Permutations!(doCopy, T)(items);
}
auto perms1(T)(T[] items) {
foreach (p; permutations!false(items)) {}
return items;
}
auto perms2(T)(T[] items) {
while (nextPermutation(items)) {}
return items;
}
int main() {
auto data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
perms1(data); // 0.90 seconds
//perms2(data); // 2.76 seconds
return data.length;
}
D code compiled with dmd 2.062alpha, -O -release -inline
-noboundscheck.
- - - - - - - - - - - - -
Extra note: maybe all such functions should be moved inside a
std.combinatorics or std.math.comb module or something similar,
with combinations range, binomial coefficient function, etc.
Another handy range is one that yields size_t[2] or
Tuple!(size_t,size_t) that represent the swaps to compute all
ajacent permutations (this code is not a range yet):
http://rosettacode.org/wiki/Permutations_by_swapping#D
Bye,
bearophile
