[plt-scheme] Total Order on sets

On Wed, Jun 3, 2009 at 1:36 AM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> Here is an idea:
>
> #|
>  Value is one of             %%
>  -- 'nat                    %% element of Nat
>  -- (cons Value Value)      %% pair of values
>  -- (listof Value)          %% setof values
> |#
>

Hi Matthias,

Thanks for the input but I guess I missed something.

> You can generate all possible shapes of a certain size or less

Not all shapes are possible. In fact sets are homogeneous so we can't
have (listof (cons 1 2) 3).

> 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.)
>

The problem is basically that I given a specification of the value:
(cons (setof 'nat) 'nat) I need to generate a total order for the
values of this type (pairs where the car is a set of integers and the
cdr a nat).
This seems to be intrinsically recursive where I assume that I have
define total orders for the elements of the pair and I start the total
order for the pair with the initial elements of the total order of its
parts: (cons (set) 0), where (set) is the emptyset.
The problem is always to know which should be the next element given
the current one assuring that:
- all elements are covered;
- and there is enough 'dispersity' of data (don't really know how to
put it) but I mean that when enumerating integers I cannot try to
enumerate first all the positives and then all the negatives. Same
with pairs, I cannot enumerate all the the pairs with the first
element and then all the pairs with the second elements because i
would never get there. With sets the same applies, I cannot enumerate
all the sets with one element first. I need somehow to intersperse all
this...

Is this even theoretically possible?


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



-- 
Paulo Jorge Matos - pocmatos at gmail.com
http://www.pmatos.net