next_permutation and cartesian product for ranges?

[H. S. Teoh]

Recently I've been working on some computational geometry code, and
noticed that Phobos doesn't have any equivalent of STL's
next_permutation. I saw there were some discussions about this back in
2010 -- did anything come of it?

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.

//

Also, I'm interested in Cartesian products of n ranges. Cartesian
products tend to be too long to explicitly construct, so it lends itself
perfectly to a range interface where the elements of the product are
computed on the fly.

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. Make a table of infinite width
and height, with rows representing one copy of the natural numbers and
columns another copy, then enumerate all elements by enumerating
diagonals. This produces a one-to-one correspondence between the natural
numbers and pairs of natural numbers, of which the rationals are a
subset (thus one has |N| ≤ |Q| ≤ |N|, proving that |N| = |Q|). For
ranges, we don't care about eliminating duplicates like 2/4 = 1/2, since
we want all possible pairs. So the infinite table looks like:

	(0,0) (1,0) (2,0) (3,0) (4,0) ...
	(0,1) (1,1) (2,1) (3,1) ...
	(0,2) (1,2) (2,2) ...
	(0,3) (1,3) ...
	(0,4) ...
	...

The diagonals are therefore:

	(0,0)
	(0,1) (1,0)
	(0,2) (1,1) (2,0)
	(0,3) (1,2) (2,1) (3,0)
	(0,4) (1,3) (2,2) (3,1) (4,0)
	...

The characteristic of the n'th diagonal is that the sum of elements in
each diagonal is equal to n. For example, the zeroth diagonal has only
(0,0) since that's the only pair that sums to 0. The first diagonal is
(0,1), (1,0): each pair sums to 1. The second diagonal: each pair sums
to 2, and so on. The general form for the i'th element of the n'th
diagonal is therefore (i, n-i), for 0 ≤ i ≤ (n-1).

So to enumerate the Cartesian product of two infinite ranges, we
enumerate its diagonals by interpreting the above pairs as indices into
the respective ranges. So, the first range can be a forward range and
the second bidirectional (since for each diagonal we need to enumerate
the second range from the n'th element down to the first). Of course, if
the first range is bidirectional and the second is forward, we can just
swap them and reverse the pairs generated.

If one or both of the ranges is finite, then we can fall back to the
naïve method of enumerating the Cartesian product, in which case we can
relax the requirement on the ranges to be just one forward range and one
input range (with the infinite range being the input range, if one of
them is infinite).

To support the Cartesian product of n ranges, we just compose multiple
binary Cartesian products.

Comments? :)


T

-- 
Many open minds should be closed for repairs. -- K5 user