H. S. Teoh:
1) To avoid excessive allocations, it would have to be a
transient range.
See the doCopy boolean template argument in my code. Note that
it's true on default. (D Zen: do the safe thing on default, and
the fast thing on request).
2) If the starting range is not sorted, then the permutation
range needs
to make a copy of the original range so that it knows when all
permutations have been enumerated. But there is no generic way
to make a
copy of a range
Isn't it possible to call array() on the input range? (Performing
array() takes a microscopic amount of time compared to computing
its permutations.)
I think this is an unfair comparison: using factorial assumes
that all array elements are unique.
It's a fair comparison because it tests a common usage case in my
code.
I'm not asking to remove nextPermutation from Phobos. I think
nextPermutation is useful, but in many cases my items are unique
(example: I make them unique before giving them to
permutations()). (And I think it's not good to slow down this
very common case because in general they aren't unique.)
The advantage of nextPermutation is that it
correctly handles duplicated elements, producing only distinct
permutations of them. It's no surprise that if you sacrifice
handling of
duplicated elements, the code will be faster.
...
(Not to mention, using factorial is limited because its value
grows too
quickly, and once your range is large enough, you will be
needing to use
BigInt to be able to deal with the factorial values without
overflow.
The current implementation of nextPermutation doesn't suffer
from this
problem.)
See above.
Bye,
bearophile
