[plt-scheme] Total Order on sets

Oops, I missed the homogeneous.

If you can encode the sets you could use one of the numerous  
enumerations for pairs that domain theoreticians (for example) employ.

-- Matthias



On Jun 3, 2009, at 10:37 AM, Paulo J. Matos wrote:

> 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