Combining infinite ranges
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Mon May 31 18:54:19 PDT 2010
On 05/31/2010 08:07 PM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at 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
More information about the Digitalmars-d
mailing list