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
