next_permutation and cartesian product for ranges?

[Andrei Alexandrescu]

On 10/9/12 1:52 PM, H. S. Teoh wrote:
> Recently I've been working on some computational geometry code, and
> noticed that Phobos doesn't have any equivalent of STL's
> next_permutation. I saw there were some discussions about this back in
> 2010 -- did anything come of it?
>
> If there is any interest in next_permutation, I'd also like to propose a
> next_even_permutation for ranges without duplicate elements. There is a
> simple way of extending Narayana Pandita's in-place algorithm for
> enumerating all permutations such that only even permutations are
> returned.

Yes, we need next_permutation. It will be up to you to convince the 
Grand Inquisition Committee of Reviewers that next_even_permutation is 
necessary and/or sufficient.

> //
>
> Also, I'm interested in Cartesian products of n ranges. Cartesian
> products tend to be too long to explicitly construct, so it lends itself
> perfectly to a range interface where the elements of the product are
> computed on the fly.
>
> Now I saw in the dlang.org search results that Cartesian products have
> been discussed before, but got roadblocked because the naïve
> implementation of Cartesian product (simply enumerate the first range,
> then popFront the second range when the first runs out and gets restored
> to the initial .save point, etc.) doesn't lend itself well to infinite
> ranges.
>
> Here's my proposed solution: we can use a trick that mathematicians use
> in set theory to prove that the cardinality of the rationals is equal to
> the cardinality of the natural numbers.
[snip]

Yah, I call that the Cantor's diagonalization trick - I reckon that's 
how he proved there are more reals than rationals: http://goo.gl/MTmnQ. 
We need that badly. Please implement pronto and let us destroy you for 
having done so.


Thanks,

Andrei