next_permutation and cartesian product for ranges?

[Andrei Alexandrescu]

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