About ranges and iterators again: implementing next_permutation

[Andrei Alexandrescu]

On 07/10/2011 04:13 PM, Max Klyga wrote:
> Several weeks ago Andrei mentioned at #d irc channel that he wanted to
> implement next_permutation STL function in Phobos.
> I thought that would be a nice excercize to implement it myself.
>
> I ported implementation mentioned in this article:
> http://marknelson.us/2002/03/01/next-permutation/
>
> At first it seemed trivial, but i failed to preserve the same
> constraints that STL implementation requires while preserving same
> efficiency.
>
> A straightforward port using random access ranges and indeces as
> iterators: http://pastie.org/2193659
>
> I tried to implement the same algorithm for bidirectional ranges, but it
> is obviously slower, because i have to shrink range's left side all the
> way, while iterators have a very nice ability: two iterators make a
> range on which algorithms can operate. This is imposible with ranges. At
> least I haven't found a way to do it.
>
> An attempt to implement next_permutation for biderectional ranges:
> http://pastie.org/2193686
> This implementation runs about 2-2.5 times slower on my machine.
>
> I think it's a nice challenge for D community to try to adapt this
> algorithm for ranges, allowing it be as fast and as generic as STL version.

I think part of the speed difference is the fact that operations on 
array ranges need to touch two words each so are more expensive. Besides 
there's a fair amount of extra churn. In the loop of the random access 
version we only have one decrement and a couple of tests, but in the 
range version there are several operations.

Here's my implementation that adds just a couple of marginal 
improvements and simplifications:

bool nextPermutation2(T)(T range)
     if (isBidirectionalRange!T && hasSwappableElements!T)
{
     if (range.walkLength(2) <= 1)
         return false;

     auto i = range.save;

     for (T jj;; i.popFront())
     {
         T ii = i.save;
         ii.popFront();

         if (ii.empty)
         {
             if (jj.empty)
             {
                 reverse(range);
                 return false;
             }
             T j = range.save;
             while (jj.front >= j.back)
                 j.popBack();
             swap(jj.front, j.back);
             jj.popFront();
             reverse(jj);
             return true;
         }

         if (i.front < ii.front)
             jj = i.save;
     }
}


Andrei