random shuffles

[Boris Borcic]

Boris Borcic wrote:
> Paul Rubin wrote:
>> Boris Borcic <bborcic at gmail.com> writes:
>>> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>>> pick a random shuffle of x with uniform distribution ?
>>
>> You really can't assume anything like that.  Sorting assumes an order
>> relation on the items being sorted, which means if a < b and b < c,
>> then a < c.  If your comparison operation doesn't preserve that
>> property then the sort algorithm could do anything, including looping
>> forever or crashing.
> 
> Not if it does the minimum number of comparisons to achieve the sort, in 
> which case it won't ever call cmp() if the result is pre-determined by 
> the order relation and previous comparisons, so that it will never get 

read "by /the assumption of an order relation/ and previous comparisons"

> from this comparison function a system of answers that's not consistent 
> with an order relation. That's obvious at least in the case where 
> random.random() == 0.5 never occurs (and at first sight even the latter 
> case shouldn't change it).

- this - the idea that /if/ the algorithm was optimal it would only sample the 
random comparison function up to a system of answers consistent with an order 
relation - is actually what prompted my question,
iow "is it good for anything ?"

Best, BB
--
"On naît tous les mètres du même monde"