[plt-scheme] Total Order on sets

On Wed, Jun 3, 2009 at 3:41 PM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> 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.
>

By encoding the sets you mean, encoding it as lists, right [a pair
where the second element is a pair or null]?

Paulo Matos

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



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