random shuffles

[Boris Borcic]

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

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