[plt-scheme] Total Order on sets

Paulo wrote:

> Is this even theoretically possible?

It's certainly theoretically possible, but there's a tradeoff between 
space and time. I thought of a solution which might be reasonable, but 
may not be optimal.

Suppose you want all pairs generated by two iterators (one for the first 
dimension and one for the second). The state will be the iterator for 
the first dimension and an integer representing the number of times it's 
been applied. To generate pairs, apply the first-dimension iterator and 
then start the second-dimension iterator from scratch and apply it as 
many times as you've applied the first one, outputting all pairs along 
the way.

If the iterator are on integers, this results in
(0,0)
(1,0) (1,1)
(2,0) (2,1) (2,2)

It's not hard to see how to generate the missing triangle separately. 
Then intersperse the two to get all pairs.

This generalizes to k dimensions. The space required is for one entry in 
each dimension, plus k integers.

To generate all tuples of any length, apply 1D, 2D, 3D, 4D... iterators 
in this pattern:

1 - 1 2 - 1 2 3 - 1 2 3 4 ...

The space required is the square of the maximum dimension reached. You 
can probably get this down to linear in the maximum dimension reached. 
It might even be possible to do better -- I bet this is a well-studied 
problem.

For sets, all the iterators are the same, and you don't want to generate 
any tuple where a later entry has "index" smaller than an earlier entry. 
Not too hard to see how to do that with the triangle idea above.

Of course, you probably have other considerations as well -- some orders 
are better than others, and may lead to nicer implementations. But it is 
certainly doable. --PR