On 10/9/12 4:46 PM, H. S. Teoh wrote:
On Tue, Oct 09, 2012 at 02:25:13PM -0400, Andrei Alexandrescu wrote:
On 10/9/12 1:52 PM, H. S. Teoh wrote:
[...]
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.
Is there much chance of this, if the algorithm only works correctly when
the input array has no duplicate elements? AFAIK there's no easy way to
ensure unique elements without introducing runtime checks.
We draw the line at memory safety. If you must assume distinct elements
and state that assumption, you're fine as long as you don't transgress
into unsafe. One alternative would be to run a O(N) check with
probability 1/N, trick that assumeSorted() does.
[...]
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.
[...]
Here it is:
-------------------------------------------------------------------------------
import std.algorithm;
import std.range;
// I wrote this 'cos I needed it. Why isn't it in std.range?
// A better name for this is probably "denest" or "denestOne", since it doesn't
// really flatten arbitrarily-nested ranges.
auto flatten(R)(R ror)
crossProduct.
if (isInputRange!R&& isInputRange!(ElementType!R))
Tab detected. System overload
