On 06/01/2010 11:34 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <[email protected]> wrote:
On 06/01/2010 09:23 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <[email protected]> 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
#!/home/andrei/bin/rdmd --shebang -unittest
import std.algorithm, std.contracts, std.range, std.stdio, std.typecons;
struct Combiner(R1, R2)
{
private:
R1 r1Orig, r1;
R2 r2Orig, r2;
enum State { done, walkR1, walkR2 }
State state;
ulong globalOffset;
ulong walkOffset;
this(R1 _r1, R2 _r2)
{
r1Orig = _r1.save;
r2Orig = _r2.save;
r1 = _r1;
r2 = _r2;
if (!_r1.empty && !_r2.empty) state = State.walkR1;
}
@property bool empty() const
{
return state == State.done;
}
@property Tuple!(ElementType!R1, ElementType!R2) front()
{
return tuple(r1.front, r2.front);
}
private void startNextEpoch()
{
assert(!empty && !r1.empty && !r2.empty);
// We also assume that r1 and r2 are both positioned in the
// outermost corner
// Global offset increment marks the new epoch
++globalOffset;
walkOffset = 0;
// Upon the new epoch we try to walk r1 first, r2 second
r2.popFront();
if (r2.empty)
{
// We can't walk r1, but there may be still some juice
// left in r1, so try to walk r2
r1.popFront();
if (r1.empty)
{
state = State.done;
}
else
{
r2 = r2Orig.save;
assert(!r2.empty);
state = State.walkR2;
}
}
else
{
// Walk r1 now
r1 = r1Orig.save;
state = State.walkR1;
}
}
void popFront()
{
enforce(!empty);
assert(!r1.empty && !r2.empty);
if (state == State.walkR1)
{
if (walkOffset == globalOffset)
{
// Special case: first corner entails no walk of r2
if (!globalOffset)
{
startNextEpoch();
}
else
{
// We're straight in the far corner, now walk r2
r2 = r2Orig.save;
state = State.walkR2;
walkOffset = 0;
}
}
else
{
// Still a ways to walk r1
r1.popFront();
if (r1.empty)
{
// r2 outlasts r1
r2.popFront();
if (r2.empty)
{
state = State.done;
}
else
{
r1 = r1Orig.save;
++globalOffset;
walkOffset = 0;
assert(state == State.walkR1);
}
}
else
{
++walkOffset;
}
}
}
else // state == State.walkR2
{
assert(state == State.walkR2);
assert(walkOffset <= globalOffset);
r2.popFront();
if (r2.empty)
{
// Continue walking r2
r1.popFront();
if (r1.empty)
{
state = State.done;
}
else
{
r2 = r2Orig.save;
++globalOffset;
walkOffset = 0;
assert(state == State.walkR2);
}
}
else if (++walkOffset >= globalOffset)
{
// We're in the outermost corner, start new epoch
startNextEpoch();
}
}
}
}
auto xproduct(R1, R2)(R1 r1, R2 r2)
{
return Combiner!(R1, R2)(r1, r2);
}
void main()
{
auto c = xproduct(iota(3), iota(5));
uint i;
foreach (e; c)
{
writeln(i++, '\t', e);
}
}
