nextPermutation and ranges

[H. S. Teoh]

On Thu, Feb 07, 2013 at 08:47:39PM +0100, bearophile wrote:
> 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).

Good point.


> >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.)

array() doesn't work on transient ranges.

But I suppose it's OK to forego that, if we're going to be safe by
default.


> >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.)
[...]

We could make a variant of nextPermutation (or a range incarnation
thereof) that assumes uniqueness. I think that would be a great addition
to Phobos.

Nevertheless, any implementation based on factorial would have to
address the issue of how to handle the exponential growth. I think it's
unacceptable for the standard library to support permutations only up to
ranges of 20 elements or less, because 21! > 2^64.


T

-- 
"Real programmers can write assembly code in any language. :-)" -- Larry Wall