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:

-------------------------------------------------------------------------------
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)
	if (isInputRange!R && isInputRange!(ElementType!R))
{
	struct Flatten(R) {
		R ror;
		ElementType!R r;

		@property bool empty() {
			if (ror.empty) return true;

			// This shenanigan is needed because operating on
			// ror.front directly sometimes doesn't work, e.g. if
			// ror.front.popFront() works on a copy of ror.front
			// and so ror is never updated.
			while (r.empty) {
				ror.popFront();
				if (ror.empty)
					return true;
				r = ror.front;
			}
			return false;
		}

		@property auto front() {
			return r.front;
		}

		void popFront() {
			r.popFront();
			while (r.empty) {
				ror.popFront();
				if (ror.empty) return;
				r = ror.front;
			}
		}
	}

	auto r = Flatten!R(ror);
	if (!ror.empty) r.r = ror.front;	// get things started
	return r;
}

// This is what I really wanted to show.
auto cartesianProd(R1,R2)(R1 range1, R2 range2)
	if (isForwardRange!R1 && isInfinite!R1 &&
	    isBidirectionalRange!(typeof(take(range2,1))) && isInfinite!R2)
{
	// Behold the awesomeness of D functional programming! ;-)
	return flatten(
		map!((int n) => zip(
			take(range1.save, n),
			retro(take(range2.save, n))
		))(sequence!"n"(1))
	);
}

void main() {
	import std.conv;
	import std.stdio;

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

	writefln("N*N = %(%s, %)", map!"[a[0], a[1]]"(N2.take(20)));

	// 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);

	writefln("odds * evens = %(%s, %)", map!"[a[0], a[1]]"(
		cartesianProd(odds, evens).take(20)));
}
-------------------------------------------------------------------------------

Destroy!


T

-- 
Ignorance is bliss... but only until you suffer the consequences!

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;
}

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

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

On Tue, Oct 09, 2012 at 05:46:41PM -0400, Andrei Alexandrescu wrote:
> 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.

The algo will never transgress into unsafe. It's just that it will produce incomplete results if the array has duplicate elements (it will fail to produce some permutations).


[...]
> >>Yah, I call that the Cantor's diagonalization trick - I reckon that's how he proved there are more reals than rationals:

Actually, this one is to prove that |Q|=|N|. The more famous Cantor diagonalization is the one where he proves that the reals are uncountable. But actually, that proof wasn't the original proof; it was something that came later. The original proof used a different method. In any case, I think we don't have to worry about Cartesian products of uncountable ranges. :-P


> >>http://goo.gl/MTmnQ. We need that badly. Please implement pronto and let us destroy you for having done so.

Please see other post.


[...]
> >// 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.

I was an idiot. I knew about std.algorithm.joiner but for some reason didn't think of it at the time. In any case, crossProduct doesn't make any sense to me... I don't see what it's got to do with flattening nested ranges.


> >	if (isInputRange!R&&  isInputRange!(ElementType!R))
> 
> Tab detected. System overload

// vim:set ts=4 sw=4 expandtab:

:-)


T

-- 
Always remember that you are unique. Just like everybody else. -- despair.com

On 10/10/2012 01:13 AM, H. S. Teoh wrote:
> 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.)
>

I usually use standard function call notation for zip. (but the mail
client wraps around the code, so I inserted a manual line break.)

On 10/9/12 7:25 PM, H. S. Teoh wrote:
> I was an idiot. I knew about std.algorithm.joiner but for some reason
> didn't think of it at the time. In any case, crossProduct doesn't make
> any sense to me... I don't see what it's got to do with flattening
> nested ranges.

I meant the resulting range spans the cross product (all combinations) of the passed-in ranges.

On another subject, I think this can be done with only input ranges - no need for bidirectional.


Andrei

On Wed, Oct 10, 2012 at 09:41:34AM -0400, Andrei Alexandrescu wrote:
> On 10/9/12 7:25 PM, H. S. Teoh wrote:
> >I was an idiot. I knew about std.algorithm.joiner but for some reason didn't think of it at the time. In any case, crossProduct doesn't make any sense to me... I don't see what it's got to do with flattening nested ranges.
> 
> I meant the resulting range spans the cross product (all combinations)
> of the passed-in ranges.

Hmm. We must be using a different set of terms, because in my understanding, a cross product is a binary operation on 3D vectors that produces a perpendicular vector. The product that produces all combinations of a set is known as a Cartesian product to me.


> On another subject, I think this can be done with only input ranges - no need for bidirectional.
[...]

In the case of finite ranges, one of the ranges can be an input range, but the other must at least be a forward range, since otherwise you could only traverse it once, so it would be impossible to combine each element with every element from the other range.

When one of the ranges is infinite, it's obviously not enough for the other range to be an input range, since you'd have to produce an infinite number of combinations per element (of the second range) before moving on to the next element, so you'd never get to it.

It should be possible to do it with both ranges being forward ranges, but it may not be very efficient -- think about it, for every element in one range, you need to combine it with every element in the other range, so when you're at, say, the 100th element of the first range, you still need to go back to the 1st, 2nd, 3rd, etc., elements in the second range. But since you can only combine it with a finite number of elements from the second range (otherwise you'll never get to the 101th element), when you get to the 101th element, you still haven't produced some of the combinations of the 100th element yet. So you'll end up needing an increasing number of save points in order to get to every possible combination -- possible but not efficient.

Using the Cantor method we can allow one range to be a forward range, and the second a range whose take(n) is a reversible range (I was wrong before: the second range doesn't need to be bidirectional, it works as long as take(n) returns a reversible range). This gives us constant space complexity. I'd say this is a pretty good solution.


T

-- 
Век живи - век учись. А дураком помрёшь.

On 10/10/12 10:27 AM, H. S. Teoh wrote:
> On Wed, Oct 10, 2012 at 09:41:34AM -0400, Andrei Alexandrescu wrote:
>> On 10/9/12 7:25 PM, H. S. Teoh wrote:
>>> I was an idiot. I knew about std.algorithm.joiner but for some reason
>>> didn't think of it at the time. In any case, crossProduct doesn't
>>> make any sense to me... I don't see what it's got to do with
>>> flattening nested ranges.
>>
>> I meant the resulting range spans the cross product (all combinations)
>> of the passed-in ranges.
>
> Hmm. We must be using a different set of terms, because in my
> understanding, a cross product is a binary operation on 3D vectors that
> produces a perpendicular vector. The product that produces all
> combinations of a set is known as a Cartesian product to me.

Same thing for sets. I agree using Cartesian is more precise.

http://www.transtutors.com/math-homework-help/set-theory/cartesian-product.aspx

>> On another subject, I think this can be done with only input ranges -
>> no need for bidirectional.
> [...]
>
> In the case of finite ranges, one of the ranges can be an input range,
> but the other must at least be a forward range, since otherwise you
> could only traverse it once, so it would be impossible to combine each
> element with every element from the other range.

Yah.

> When one of the ranges is infinite, it's obviously not enough for the
> other range to be an input range, since you'd have to produce an
> infinite number of combinations per element (of the second range) before
> moving on to the next element, so you'd never get to it.

Something like that.

> It should be possible to do it with both ranges being forward ranges,
> but it may not be very efficient -- think about it, for every element in
> one range, you need to combine it with every element in the other range,
> so when you're at, say, the 100th element of the first range, you still
> need to go back to the 1st, 2nd, 3rd, etc., elements in the second
> range. But since you can only combine it with a finite number of
> elements from the second range (otherwise you'll never get to the 101th
> element), when you get to the 101th element, you still haven't produced
> some of the combinations of the 100th element yet. So you'll end up
> needing an increasing number of save points in order to get to every
> possible combination -- possible but not efficient.
>
> Using the Cantor method we can allow one range to be a forward range,
> and the second a range whose take(n) is a reversible range (I was wrong
> before: the second range doesn't need to be bidirectional, it works as
> long as take(n) returns a reversible range). This gives us constant
> space complexity. I'd say this is a pretty good solution.

I'm still thinking of Cantor's method, just a different schedule of spanning the triangle. Multiple save points are necessary. Consider you span the triangle in squares of increasing side. For each side size you first walk along one dimension, then walk along the other.


Andrei

On 10/10/12 10:59 AM, Andrei Alexandrescu wrote:
> I'm still thinking of Cantor's method, just a different schedule of
> spanning the triangle. Multiple save points are necessary.

I meant "Multiple save points are NOT necessary."

Andrei