[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