nextPermutation and ranges

[bearophile]

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