next_permutation and cartesian product for ranges?

[H. S. Teoh]

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!