next_permutation and cartesian product for ranges?

[H. S. Teoh]

On Tue, Oct 09, 2012 at 11:24:27PM +0200, Timon Gehr wrote:
[...]
> That's cute. =)
> flatten is in std.algorithm and is called joiner.

Ahahahaha... I knew joiner existed; why didn't I think of it. :P


> 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;
> }
[...]

Ack! UFCS overload! ;-) (just kidding... it's actually a lot easier to
read with UFCS.)

And I think that trailing comma should be a ')'.

Alright, now to take care of the case where one of the ranges is not
infinite:

-------------------------------------------------------------------------------
import std.algorithm;
import std.range;

auto cartesianProd(R1,R2)(R1 range1, R2 range2)
{
    // I decided to hoist the conditions in here 'cos the cases overlap.
    // Probably still need to factor them and put them in the sig
    // constraint. But hey, this works for now.
    static if (isForwardRange!R1 && isInfinite!R1 &&
        isBidirectionalRange!(typeof(take(range2,1))) && isInfinite!R2)
    {
        // Courtesy of Timon Gehr
        return sequence!"n"(cast(size_t)1)
            .map!((size_t n) => range1.save.take(n)
                                .zip(range2.save.take(n).retro))
            .joiner;
    }
    else static if (isInputRange!R1 && !isInfinite!R1 && isForwardRange!R2)
    {
	// A one-liner! Gotta love D's functional programming features!
        return range2.map!((ElementType!R2 a) => zip(range1.save, repeat(a)))
            .joiner;
    }
    else static if (isInputRange!R2 && !isInfinite!R2 && isForwardRange!R1)
    {
	// I could've aliased this to the previous case with tuples
	// swapped, but why bother when you can do it the direct way?
        return range1.map!((ElementType!R1 a) => zip(repeat(a), range2.save))
            .joiner;
    }
    else static assert(0);
}

unittest {
    // A simple test case: Cartesian product of the set of natural numbers with
    // itself.
    auto N = sequence!"n"(0);
    auto N2 = cartesianProd(N, N);

    assert(map!"[a[0],a[1]]"(N2.take(10)).equal([[0, 0], [0, 1], [1, 0],
        [0, 2], [1, 1], [2, 0], [0, 3], [1, 2], [2, 1], [3, 0]]));

    // Let's prove that it works for more than just the natural numbers
    auto odds = sequence!"2*n+1"(0);
    auto evens = sequence!"2*n"(0);

    assert(map!"[a[0],a[1]]"(cartesianProd(odds, evens).take(10))
        .equal([[1, 0], [1, 2], [3, 0], [1, 4], [3, 2], [5, 0], [1, 6], [3, 4],
                [5, 2], [7, 0]]));

    // Test finite cases
    auto arr = [1,2,3];
    assert(cartesianProd(arr,N)
        .take(10)
        .map!"[a[0],a[1]]"
        .equal([[1, 0], [2, 0], [3, 0], [1, 1], [2, 1], [3, 1], [1, 2], [2, 2],
                [3, 2], [1, 3]]));

    assert(cartesianProd(N,arr)
        .take(10)
        .map!"[a[0],a[1]]"
        .equal([[0, 1], [0, 2], [0, 3], [1, 1], [1, 2], [1, 3], [2, 1], [2, 2],
                [2, 3], [3, 1]]));

    auto barr = [4,5,6];
    assert(cartesianProd(arr,barr)
        .map!"[a[0],a[1]]"
        .equal([[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6], [2, 6],
                [3, 6]]));
}

// To keep Andrei happy:
// vim:set ts=4 sw=4 expandtab:
-------------------------------------------------------------------------------

Destroy!!


T

-- 
Nothing in the world is more distasteful to a man than to take the path that leads to himself. -- Herman Hesse