View mode: basic / threaded / horizontal-split · Log in · Help
June 01, 2010
Re: Combining infinite ranges
On 05/31/2010 08:54 PM, Andrei Alexandrescu wrote:
> On 05/31/2010 08:07 PM, Simen kjaeraas wrote:
>> Andrei Alexandrescu <SeeWebsiteForEmail@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.

I'm off by one there, but you got the idea :o).

Andrei
June 01, 2010
Re: Combining infinite ranges
Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> 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.

All forward ranges should be doable, too. One input range also, as long
as no other range is infinite. In the case of all forward ranges, elements
of each should be visited in order, though. I believe this to be possible,
but not at all easy.

I had to abandon my original idea, as it proved fundamentally flawed.

I believe that for the case of 0 or 1 infinite ranges, the approach used
in the already supplied version is good enough. It also works if one range
is an (optionally infinite) input range. Well, except that it does not
without some rewrites...

For more than one infinite range, Cantor's diagonalization approach
should work, but only if all ranges or all except one are random-access.

-- 
Simen
June 01, 2010
Re: Combining infinite ranges
On 05/31/2010 10:51 PM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>> 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.
>
> All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

Andrei
June 01, 2010
Re: Combining infinite ranges
Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

>> All forward ranges should be doable, too.
>
> How would the spanning strategy work for two forward infinite ranges?

In a complex, horrible way?

0. Save initial states (position = 0)
1. Pop first until past the position of the other
2. Restore other
3. Pop other until past the position of the first
4. Restore first
6. Goto 1.

Screw that, as you cannot save positions. Well, I guess a long should
be enough for most, but it might not be. As long as there is no way
to compare positions, 'tis unpossible.

If we accept saving the position (the number of pops), this approach
should be applicable to any number of ranges.

--
Simen
June 01, 2010
Re: Combining infinite ranges
On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>>> All forward ranges should be doable, too.
>>
>> How would the spanning strategy work for two forward infinite ranges?
>
> In a complex, horrible way?
>
> 0. Save initial states (position = 0)
> 1. Pop first until past the position of the other
> 2. Restore other
> 3. Pop other until past the position of the first
> 4. Restore first
> 6. Goto 1.
>
> Screw that, as you cannot save positions. Well, I guess a long should
> be enough for most, but it might not be. As long as there is no way
> to compare positions, 'tis unpossible.
>
> If we accept saving the position (the number of pops), this approach
> should be applicable to any number of ranges.

It's ok to store positions in ulong objects. Most uses of infinite range 
combinations use only the first few elements; the computation will 
anyway take a very, very long time when any of the ranges overflows a ulong.

That being said, I didn't understand the algorithm. What is its 
complexity? From what I understand there's a lot of looping going on. We 
need something that makes progress in O(1).


Andrei
June 01, 2010
Re: Combining infinite ranges
Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>>> All forward ranges should be doable, too.
>>>
>>> How would the spanning strategy work for two forward infinite ranges?
>>
>> In a complex, horrible way?
>>
>> 0. Save initial states (position = 0)
>> 1. Pop first until past the position of the other
>> 2. Restore other
>> 3. Pop other until past the position of the first
>> 4. Restore first
>> 6. Goto 1.
>>
>> Screw that, as you cannot save positions. Well, I guess a long should
>> be enough for most, but it might not be. As long as there is no way
>> to compare positions, 'tis unpossible.
>>
>> If we accept saving the position (the number of pops), this approach
>> should be applicable to any number of ranges.
>
> It's ok to store positions in ulong objects. Most uses of infinite range  
> combinations use only the first few elements; the computation will  
> anyway take a very, very long time when any of the ranges overflows a  
> ulong.

With the algorithm (attempted) explained above, it's actually 2^128, which
is acceptably high, I think.

> That being said, I didn't understand the algorithm. What is its  
> complexity? From what I understand there's a lot of looping going on. We  
> need something that makes progress in O(1).

Should be O(1). Each pop in the described algorithm is a call to popFront:

void popFront( ) {
    ranges[active].popFront;
    position[active]++;
    if (position[active] > position[inactive]) {
        active = !active;
        position[active] = 0;
        ranges[active] = savedRange[active];
    }
}

-- 
Simen
June 01, 2010
Re: Combining infinite ranges
On 06/01/2010 11:34 AM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
>>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>>>> All forward ranges should be doable, too.
>>>>
>>>> How would the spanning strategy work for two forward infinite ranges?
>>>
>>> In a complex, horrible way?
>>>
>>> 0. Save initial states (position = 0)
>>> 1. Pop first until past the position of the other
>>> 2. Restore other
>>> 3. Pop other until past the position of the first
>>> 4. Restore first
>>> 6. Goto 1.
>>>
>>> Screw that, as you cannot save positions. Well, I guess a long should
>>> be enough for most, but it might not be. As long as there is no way
>>> to compare positions, 'tis unpossible.
>>>
>>> If we accept saving the position (the number of pops), this approach
>>> should be applicable to any number of ranges.
>>
>> It's ok to store positions in ulong objects. Most uses of infinite
>> range combinations use only the first few elements; the computation
>> will anyway take a very, very long time when any of the ranges
>> overflows a ulong.
>
> With the algorithm (attempted) explained above, it's actually 2^128, which
> is acceptably high, I think.
>
>> That being said, I didn't understand the algorithm. What is its
>> complexity? From what I understand there's a lot of looping going on.
>> We need something that makes progress in O(1).
>
> Should be O(1). Each pop in the described algorithm is a call to popFront:
>
> void popFront( ) {
> ranges[active].popFront;
> position[active]++;
> if (position[active] > position[inactive]) {
> active = !active;
> position[active] = 0;
> ranges[active] = savedRange[active];
> }
> }

I still haven't understood your explanation, but I think I figured a 
different way to reach the same solution. The idea is to crawl the space 
by adding layers on top of a hypercube of increasing side, starting from 
the origin corner.

This is an absolutely awesome problem. I attach an implementation for 
two ranges. It's quite a bit more messy than I'd hope, so generalization 
to n ranges should be preceded by cleaning up the abstractions used. I 
think your solution already has said cleanups!

The output of the program is:

0	Tuple!(uint,uint)(0, 0)
1	Tuple!(uint,uint)(0, 1)
2	Tuple!(uint,uint)(1, 1)
3	Tuple!(uint,uint)(1, 0)
4	Tuple!(uint,uint)(0, 2)
5	Tuple!(uint,uint)(1, 2)
6	Tuple!(uint,uint)(2, 2)
7	Tuple!(uint,uint)(2, 0)
8	Tuple!(uint,uint)(2, 1)
9	Tuple!(uint,uint)(0, 3)
10	Tuple!(uint,uint)(1, 3)
11	Tuple!(uint,uint)(2, 3)
12	Tuple!(uint,uint)(0, 4)
13	Tuple!(uint,uint)(1, 4)
14	Tuple!(uint,uint)(2, 4)


Andrei
June 01, 2010
Re: Combining infinite ranges
On Tue, Jun 1, 2010 at 19:54, Andrei Alexandrescu <
SeeWebsiteForEmail@erdani.org> wrote:

> I thought about this some more, and it's more difficult and more
interesting than I thought.

Yeah, that's why I proposed it as a challenge.  You guys sure seem to like
this :)
What's interesting, is that it may even be useful :)


It's ok to store positions in ulong objects. Most uses of infinite

> range combinations use only the first few elements; the computation
>>> will anyway take a very, very long time when any of the ranges
>>> overflows a ulong.
>>>
>>
Quite...


>
> I still haven't understood your explanation, but I think I figured a
> different way to reach the same solution. The idea is to crawl the space by
> adding layers on top of a hypercube of increasing side, starting from the
> origin corner.
>

Like this?

01234
11234
22234
33334
44444

where you have layer #0, #1, ...

In fact, any method to iterate on a finite but growing space without going
onto the already produced values is OK. You could iterate on an hypercube,
then duplicate it to make it n times bigger and recurse:

01 22 3333
11 22 3333
22 22 3333
22 22 3333
3333
3333 ...
3333
3333

I think your solution is viable, because you always iterate on 'square'
shapes, that's a good idea. Its only drawback is that the elements are
produced in a less natural order, but really, who cares: you just want to
take a finite part of an infinite range without closing any door while doing
so.
Going full diagonal is more difficult: you must find a way to peel of the
slices.

I encountered this while reading some on Haskell and enumerating infinite
ranges, but the only implentation I know of for diagonals is here:
http://hackage.haskell.org/packages/archive/level-monad/0.3.1/doc/html/Control-Monad-Levels.html

Related to this, I've something that takes 'hyperslices' from ranges of
ranges of ... (of whatever rank), but only
'vertical' or 'horizontal' (perpendicular to the normal basis of ranges of
ranges...)

I also have a n-dim generalization of take: take(rangeOfRanges, 2,3,4, ...)
and for drop and slice.
I think it's doable to preduce something akin to your layers than way, or
maybe my suggestion on blocks. A combination of takes and drops should
produce
finite cubic shapes that can then be iterated.



> This is an absolutely awesome problem.


Man, don't you have some boring stuff to do instead?

I also found the (simple?) problem to enumerate a range of ranges to be more
interesting than I thought.
Given a range of ranges ... of ranges, of whatever rank, recursively
enumerate it:

[[a,b,c],[d,e,f],[g,h,i]]

produce:

(a,0,0),(b,0,1), (c,0,2),(d,1,0), ...

the coordinates of each element, if you will. I have a working version now,
but it sure taught me that my vision of recursion was flawed.



I attach an implementation for two ranges. It's quite a bit more messy than
> I'd hope, so generalization to n ranges should be preceded by cleaning up
> the abstractions used. I think your solution already has said cleanups!
>

It's good if you can make it to more than two ranges, but I think 2 is
already quite useful.


> The output of the program is:
>
> 0       Tuple!(uint,uint)(0, 0)
> 1       Tuple!(uint,uint)(0, 1)
> 2       Tuple!(uint,uint)(1, 1)
> 3       Tuple!(uint,uint)(1, 0)
> 4       Tuple!(uint,uint)(0, 2)
> 5       Tuple!(uint,uint)(1, 2)
> 6       Tuple!(uint,uint)(2, 2)
> 7       Tuple!(uint,uint)(2, 0)
> 8       Tuple!(uint,uint)(2, 1)
> 9       Tuple!(uint,uint)(0, 3)
> 10      Tuple!(uint,uint)(1, 3)
> 11      Tuple!(uint,uint)(2, 3)
> 12      Tuple!(uint,uint)(0, 4)
> 13      Tuple!(uint,uint)(1, 4)
> 14      Tuple!(uint,uint)(2, 4)
>
>
> Seems good to me. I see the layers, like in the Matrix.
If you ever put that in Phobos, make it a secondary function compared to a
standard combination, or use a policy to let the user dicide to iterate
along layers. Most of the time, you just want the standard 'digit-like' way
to iterate on n ranges.

I'll have a look at your code.

Philippe
June 01, 2010
Re: Combining infinite ranges
On Tue, 01 Jun 2010 13:54:01 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail@erdani.org> wrote:

> The output of the program is:
>
> 0	Tuple!(uint,uint)(0, 0)
> 1	Tuple!(uint,uint)(0, 1)
> 2	Tuple!(uint,uint)(1, 1)
> 3	Tuple!(uint,uint)(1, 0)
> 4	Tuple!(uint,uint)(0, 2)
> 5	Tuple!(uint,uint)(1, 2)
> 6	Tuple!(uint,uint)(2, 2)
> 7	Tuple!(uint,uint)(2, 0)
> 8	Tuple!(uint,uint)(2, 1)
> 9	Tuple!(uint,uint)(0, 3)
> 10	Tuple!(uint,uint)(1, 3)
> 11	Tuple!(uint,uint)(2, 3)
> 12	Tuple!(uint,uint)(0, 4)
> 13	Tuple!(uint,uint)(1, 4)
> 14	Tuple!(uint,uint)(2, 4)

It looks like you're missing some iterations there.

-Steve
June 01, 2010
Re: Combining infinite ranges
On 06/01/2010 04:06 PM, Steven Schveighoffer wrote:
> On Tue, 01 Jun 2010 13:54:01 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> The output of the program is:
>>
>> 0 Tuple!(uint,uint)(0, 0)
>> 1 Tuple!(uint,uint)(0, 1)
>> 2 Tuple!(uint,uint)(1, 1)
>> 3 Tuple!(uint,uint)(1, 0)
>> 4 Tuple!(uint,uint)(0, 2)
>> 5 Tuple!(uint,uint)(1, 2)
>> 6 Tuple!(uint,uint)(2, 2)
>> 7 Tuple!(uint,uint)(2, 0)
>> 8 Tuple!(uint,uint)(2, 1)
>> 9 Tuple!(uint,uint)(0, 3)
>> 10 Tuple!(uint,uint)(1, 3)
>> 11 Tuple!(uint,uint)(2, 3)
>> 12 Tuple!(uint,uint)(0, 4)
>> 13 Tuple!(uint,uint)(1, 4)
>> 14 Tuple!(uint,uint)(2, 4)
>
> It looks like you're missing some iterations there.
>
> -Steve

There should be 5 * 3 = 15 iterations.

Andrei
1 2 3 4 5 6
Top | Discussion index | About this forum | D home