Combining infinite ranges

[Andrei Alexandrescu]

On 06/01/2010 11:34 AM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
>>> Andrei Alexandrescu <SeeWebsiteForEmail at 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.d
Type: text/x-dsrc
Size: 3992 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100601/b27d9ab4/attachment-0001.d>