[Challenge] implementing the ambiguous operator in D

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Tue Sep 7 08:05:20 PDT 2010


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


More information about the Digitalmars-d mailing list