next_permutation and cartesian product for ranges?

[Timon Gehr]

On 10/09/2012 10: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.
>
>
> [...]
>>> 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:
>
> [snip code snippet]
>
> Destroy!
>
>
> T
>

That's cute. =)
flatten is in std.algorithm and is called joiner. Also, you need to be 
careful with index types.
I'd suggest:

import std.algorithm, std.range;

auto cartesianProd(R1,R2)(R1 range1, R2 range2)
if (isForwardRange!R1 && isInfinite!R1 &&
     isBidirectionalRange!(typeof(take(range2,1))) && isInfinite!R2)
{
	return sequence!"n"(cast(size_t)1).map!(
		(size_t n)=>range1.save.take(n) // need to specify param type. DMD bug.
		.zip(range2.save.take(n).retro),
	).joiner;
}