nextPermutation and ranges

[bearophile]

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