On 09/07/2010 02:43 AM, Peter Alexander wrote:
I agree with Andrei here, building hypercubes makes more sense, and feels like
it has more structure. It
also has the nice property that, once you've seen a (n+1)th element of any
range then you have already
explored the entire product of the first n elements of every range, kind of
like how the colex ordering
works.
But which way would you add the successive "shells"?
Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order?
The algorithm builds one hyperplane at a time. At level k, there are n
hyperplanes to build, each of which keeps exactly one range positioned
on the kth element, and all others iterate from their first up to their
kth element. Whenever you reached the corner of the hypercube (all
ranges are at the kth position), you start building the next hyperplane.
When all other hyperplanes are built, you popFront() the first range,
reset all others, and start building the next shell.
btw, what are some real-world uses of the cartesian product of infinite ranges?
I can't think of any off
the top of my head.
It's great for various solution-searching algorithms, like the example
given (lazily generate solutions to the equation x * y = 8). Even for
finite ranges of moderate size, exploring two iota()s in the naive order
(keep one fixed and exhaust all others) most often takes a long time to
find anything interesting. That's why I think finding a solid method to
iterate the cartesian product is important even for finite ranges.
Andrei
