# [plt-scheme] Total Order on sets

 From: Prabhakar Ragde (plragde at uwaterloo.ca) Date: Wed Jun 3 11:49:39 EDT 2009 Previous message: [plt-scheme] Total Order on sets Next message: [plt-scheme] How Hacker News was hacked Messages sorted by: [date] [thread] [subject] [author]

```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

```

 Posted on the users mailing list. Previous message: [plt-scheme] Total Order on sets Next message: [plt-scheme] How Hacker News was hacked Messages sorted by: [date] [thread] [subject] [author]