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

To be more convincing... assume the algorithm is optimal and calls
cmp(x,y). Either the previous calls (+ assuming order relation) give no 
conclusion as to the possible result of the call, in which case the result can't 
contradict an order relation; or the previous calls (+assumption) provide only 
partial information; iow the algorithm knows for example x<=y and needs to 
determine which of x<y or x==y is the case; in which situation the comparison 
function could break the assumption of an order relation by answering eg "x>y".

But is it possible for a sort algorithm assuming an order relation to attain eg 
x<=y but neither x<y nor x==y using calls to the comparison function involving 
either x or y and some other variables ? No, since the axiom of order applies to 
data that never has the form of weak inequalities and thus will never infer an 
inequality that's not strong.

Ok, this isn't well written, but I have to run.

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