[plt-scheme] Total Order on sets
Hi all,
I am in the middle of a problem which is half mathematical, half scheming...
I have three types of values to handle: integers, pairs of values and
homogeneous sets of values so examples of values are:
1
(1 . 2)
{1}
{1, 2, 3}
{(1 . 2), (1 . 3)}
({1,2} . {1,2})
I need to define a way to enumerate all the possible values just by
knowing what kind of value it is... This seems to be equivalent has
defining a total order on the values. I need an initial value and a
next function that returns my next value.
For integers the problem seems trivial, it consists in having a
closure that keeps the current value and produces:
Init = 0
Seq = 0, 1, -1, 2, -2, 3, -3 ...
(let ([n 0])
(lambda ()
(cond [(= n 0)
(set! n 1)
n]
[(> n 0)
(set! n (+ n 1))
n]
[else
(set! n (+ (- n) 1))
n])))
For pairs, is more complicated but since we can assume the values of
the pair have a total order:
Init = (Init . Init)
If to simplify we think of integers then we could draw a spiral in a
2d-axis by generating:
(0 . 0), (1 . 0), (1 . 1), (0 . 1), (-1 . 1), (-1 . 0)...
but the problem is that we have only a next function, not a previous
so we can reduce everything to the first quadrant and do:
(0 . 0), (1. 0), (0 . 1), (1 . 1), (2 . 0), (0 . 2), (2 . 1), (2 . 2),
(1 . 2), ... And for each of these we intercalate with their
counterparts on the other quadrants.
However, this only seems to work for the case of numbers, not of pairs
of sets since, there is not afaict, a counterpart in other quadrants.
Now, set are even harder... It seems to be possible to do it by
starting with the emptyset but I cannot tell a way to do it or
implement it. One requirement is obviously in terms of sets of
integers that it won't generate all sets with one element, then all
with two elements and then all with 3 but that intercalates them all
in the same sense that pairs of integers don't go:
(0 . 0), (1 . 0), (2 . 0), (3 . 0)... (inf+ . 0)
In regard to sets it would be good if the generator doesn't produce
{1, 2} if it produced already {2, 1}, of course.
If you have any idea on how to do this efficiently I would appreciate
some input.
Cheers,
--
Paulo Jorge Matos - pocmatos at gmail.com
http://www.pmatos.net