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
