June 01, 2010 Re: Combining infinite ranges | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | ```
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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Simen kjaeraas | ```
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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Simen kjaeraas | ```
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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Simen kjaeraas Attachments: | ```
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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu Attachments: - text/html part
| 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Andrei Alexandrescu | 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 | ||||
---|---|---|---|---|

| ||||

Posted in reply to Steven Schveighoffer | ```
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
``` |