• Max Klyga (21/21) Jul 10 2011 Several weeks ago Andrei mentioned at #d irc channel that he wanted to
• bearophile (4/6) Jul 10 2011 What about instead a range, that given an array of items, yields lazily ...
• Andrei Alexandrescu (4/10) Jul 10 2011 Better yet, make it an input range that modifies the parameter in-place....
• Andrei Alexandrescu (38/58) Jul 11 2011 I think part of the speed difference is the fact that operations on

Max Klyga <max.klyga gmail.com> writes:

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.

bearophile <bearophileHUGS lycos.com> writes:

Max Klyga Wrote:

 Several weeks ago Andrei mentioned at #d irc channel that he wanted to 
 implement next_permutation STL function in Phobos.

What about instead a range, that given an array of items, yields lazily all its
permutations, creating a new array each time on default, and using the same
array on (compile-time) request?

Bye,
bearophile

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 7/10/11 4:35 PM, bearophile wrote:
 Max Klyga Wrote:

 Several weeks ago Andrei mentioned at #d irc channel that he wanted
 to implement next_permutation STL function in Phobos.

 What about instead a range, that given an array of items, yields
 lazily all its permutations, creating a new array each time on
 default, and using the same array on (compile-time) request?

Better yet, make it an input range that modifies the parameter in-place. 
Then creating new arrays etc. is easy on the user side.

Andrei

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

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