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
