www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - About ranges and iterators again: implementing next_permutation

reply 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.
Jul 10 2011
next sibling parent reply 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
Jul 10 2011
parent 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
Jul 10 2011
prev sibling parent 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
Jul 11 2011