On 05/31/2010 08:07 PM, Simen kjaeraas wrote:
Andrei Alexandrescu <seewebsiteforem...@erdani.org> wrote:
Yah, there's no argument that infinite ranges must be allowed by a
n-way cross-product. It reminds one of Cantor's diagonalization, just
in several dimensions. Shouldn't be very difficult, but it only works
if all ranges except one are forward ranges (one can be an input range).
Might I coerce you into indulging some more detail on this idea? I'm
afraid my knowledge of the diagonal method is sadly lacking, and some
reading on the subject did not give me satisfactory understanding of
its application in the discussed problem.
Way I thought of doing it is save the highest position this far of each
range, then in popFront see if we're past it. If we are, reset this
range, and pop from the next range up, recursively.
I thought about this some more, and it's more difficult and more
interesting than I thought.
Cantor enumerated rational numbers the following way: first come all
fractions that have numerator + denominator = 1. That's only one
rational number, 1/1. Then come all fractions that have num + denom = 2.
That gives 1/2 and 2/1. Then come all fractions that have num + denom =
3, and so on.
Using this enumeration method he proved that rational numbers are
countable so in some way they are not more "numerous" than natural
numbers, which was an important result.
With ranges, the trick should be similar: although individual ranges may
be infinite, they are composed in a simple, countable manner.
Generalizing Cantor's enumeration technique to n ranges, note that the
enumeration goes through elements such that the sum of their offsets
from the beginning of the ranges is constant.
So for two ranges, we first select pairs that have their offsets sum to
0. That is (0, 0). Then we select pairs of offsets summing to 1: (0, 1)
and (1, 0). Then same for 2: (0, 2), (1, 1), (2, 0). And so on.
The problem is that in order to make sure offsets are constant, forward
ranges are not enough. If all ranges involved had random access, the
problem would be trivially solvable. The trick is pushing that envelope;
for example, it's possible to make things work with one forward range
and one random-access range, and so on.
This is bound to be an interesting problem. Please discuss any potential
solutions here.
Andrei
