[plt-scheme] Total Order on sets

Here is an idea:

#|
  Value is one of             %%
   -- 'nat                    %% element of Nat
   -- (cons Value Value)      %% pair of values
   -- (listof Value)          %% setof values
|#

You can generate all possible shapes of a certain size or less
if you ignore integers:

  'nat, '(), (cons 'nat 'nat), (list 'nat), (list 'nat 'nat), (cons  
'nat (cons 'nat 'nat)), (cons (cons 'nat 'nat) 'nat), ...

Once you have all these shapes, you know that you can get all the  
elements of your class of data by replacing 'nat with integers,  
though you ,ay want to superimpose a uniqueness condition on the set  
representation. (Not needed, depending on how you look for and delete  
elements.)

-- Matthias





On Jun 2, 2009, at 8:10 PM, Paulo J. Matos wrote:

> 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
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme