[plt-scheme] Re: please help with generating random permutation

From: Will M Farr (farr at MIT.EDU)
Date: Sun Sep 13 12:49:06 EDT 2009

Sigrid,

These ideas sound very good in practice.  (And I'm not entirely sure  
what the "OS approach" is either, but perhaps, as you guessed,  
Matthias is thinking of your workers as OS threads.)  You may not be  
aware, but your problem is one of a class of problems that are an  
active area of research in math:

http://en.wikipedia.org/wiki/Fair_division

You might enjoy reading about some of the algorithms mathematicians  
have discovered to partition resources "fairly".

Will

On Sep 13, 2009, at 12:40 PM, keydana at gmx.de wrote:

> I'm  not sure what the OS approach would be? Do you mean process  
> scheduling algorithms?
>
> About the randomness vs. fairness distinction (don't know which word  
> to use here, "dichotomy" surely not, but are they perhaps  
> orthogonal? There's surely quite some philosophical discussion of  
> this topic),  perhaps I should really have thought about this before  
> doing the coding.
>
> In fact what I did "intuitively" was mixing both things up, starting  
> by shuffling the input list (so, starting with the "randomness"  
> side), but then taking into account the selection from the previous  
> week and trying to select people who had not been chosen then (so,  
> deviating in a direction of what I thought was "fairness"). Because  
> of this, unfortunately, the angry colleague really had a chance of  
> 1/3 of being drawn on Monday - but as he did not know why, he  
> attributed it to his name being first in the alphabet, this was bad  
> luck for me :-;
>
> So I proposed (at least) the following possible changes (there's no  
> reactions yet):
> - take out the taking into account of the previous week ("back to  
> random")
> - add the preferences (less random, but hopefully more fair)
> - do the drawings for 2 weeks at once, having as a constraint that  
> as few people as possible be drawn twice (given the fact that we  
> have less than 10 possible "victims"). Perhaps this is even the best  
> combination of randomness & fairness (it would be random but ALSO  
> seem quite fair I guess)
>
> Ciao
> Sigrid
>
>
>
>
>
> Am 13.09.2009 um 17:27 schrieb Shriram Krishnamurthi:
>
>> I think Sigrid is saying that it wouldn't -- I believe that's what
>> she's calling "uniformity".
>>
>> On Sun, Sep 13, 2009 at 10:34 AM, Matthias Felleisen
>> <matthias at ccs.neu.edu> wrote:
>>>
>>> Would some OS-style approach to office fairness help here?
>>>
>>>
>>> On Sep 13, 2009, at 5:35 AM, keydana at gmx.de wrote:
>>>
>>>> Hi Thomas,
>>>>
>>>> I'm not so sure about the fairness. I think it's not always easy  
>>>> to define
>>>> what really IS fair in a given situation.
>>>> Personally,  I would see fairness less in the line of "uniformity"
>>>> (everyone gets the same amount of every piece, whether he likes a  
>>>> piece or
>>>> not) than of  "to each according to his needs" (not being a Marxist
>>>> otherwise, this sentence I really like).
>>>>
>>>> For example in this situation, what I originally proposed was to  
>>>> have
>>>> everyone who wants state his preferences regarding weekdays (with  
>>>> the amb
>>>> operator I use, this would be easy to add). Up till now, there  
>>>> was not much
>>>> resonance for this, but perhaps it's because people tend to  
>>>> assume they have
>>>> similar preferences or needs - which in my experience need not be  
>>>> true at
>>>> all. E.g. in this example, I would in fact prefer to be ALWAYS  
>>>> chosen on
>>>> Mondays :-;
>>>>
>>>> Cheers,
>>>> Sigrid
>>>>
>>>>
>>>>
>>>> Am 12.09.2009 um 21:37 schrieb Thomas Holubar:
>>>>
>>>>> Hi Sigrid!
>>>>>
>>>>>> thanks a lot, this helped me very much (both in understanding  
>>>>>> and in
>>>>>> giving me the confidence to defend my code)!
>>>>>
>>>>> I'm sure you'll have plenty nice - and entertaining -  
>>>>> discussions! ;-)
>>>>>
>>>>> So FWIW:
>>>>> Your colleague likely complains that the schedule your program  
>>>>> generates
>>>>> is not *fair*. You in turn claim it to be *random*. And since  
>>>>> both of you
>>>>> are probably right there's little chance you'll eventually come  
>>>>> to a
>>>>> satisfactory conclusion.
>>>>>
>>>>> Taking for granted that my understanding of fairness is  
>>>>> compatible with
>>>>> yours (and your colleague's) then fairness and randomness are  
>>>>> incompatible.
>>>>>
>>>>> YC explained this in more detail already.
>>>>>
>>>>> So, if you want happy colleagues make it fair, not random.
>>>>>
>>>>> Cheers,
>>>>> Thomas
>>>>
>>>> _________________________________________________
>>>> For list-related administrative tasks:
>>>> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>>
>>> _________________________________________________
>>> For list-related administrative tasks:
>>> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>>
>
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 203 bytes
Desc: This is a digitally signed message part
URL: <http://lists.racket-lang.org/users/archive/attachments/20090913/2c7f26e5/attachment.sig>

Posted on the users mailing list.