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.
