random shuffles

[Boris Borcic]

does

x.sort(cmp = lambda x,y : cmp(random.rand om(),0.5))

pick a random shuffle of x with uniform distribution ?

Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?

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

[Peter Otten]

Boris Borcic wrote:

does

x.sort(cmp = lambda x,y : cmp(random.rand om(),0.5))

pick a random shuffle of x with uniform distribution ?

Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite
confortable with the intuition... can anyone think of a more solid
argumentation ?

Anecdotal evidence suggests the answer is no:

>>histo = {}
for i in xrange(1000):

.... t = tuple(sorted(ra nge(3), lambda x, y: cmp(random.rand om(), 0.5)))
.... histo[t] = histo.get(t, 0) + 1
....

>>sorted(histo. values())

[60, 62, 64, 122, 334, 358]

versus:

>>histo = {}
for i in xrange(1000):

.... t = tuple(sorted(ra nge(3), key=lambda x: random.random() ))
.... histo[t] = histo.get(t, 0) + 1
....

>>sorted(histo. values())

[147, 158, 160, 164, 183, 188]

Peter

[Dustan]

Boris Borcic wrote:

does

x.sort(cmp = lambda x,y : cmp(random.rand om(),0.5))

pick a random shuffle of x with uniform distribution ?

Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?

Why not use the supplied shuffle method?

random.shuffle( x)

[Iain King]

Dustan wrote:

Boris Borcic wrote:

does

x.sort(cmp = lambda x,y : cmp(random.rand om(),0.5))

pick a random shuffle of x with uniform distribution ?

Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?

Why not use the supplied shuffle method?

random.shuffle( x)

or check out this thread:
http://groups.google.com/group/comp....vc=2&q=shuffle

Iain

[Tim Peters]

[ Boris Borcic]

x.sort(cmp = lambda x,y : cmp(random.rand om(),0.5))

pick a random shuffle of x with uniform distribution ?

Say len(x) == N. With Python's current sort, the conjecture is true
if and only if N <= 2.

Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort,

No idea what that could mean in a rigorous, algorithm-independent way.

I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?

If a list is already sorted, or reverse-sorted, the minimum number of
comparisons needed to determine that is N-1, and Python's current sort
achieves that. It first looks for the longest ascending or descending
run. If comparison outcomes are random, it will decide "yes, already
sorted" with probability 1/2**(N-1), and likewise for reverse-sorted.
When N 2, those are larger than the "correct" probabilities 1/(N!).
So., e.g., when N=3, the sort will leave the list alone 1/4th of the
time (and will reverse the list in-place another 1/4th). That makes
the identity and reversal permutations much more likely than "they
should be", and the bias is worse as N increases.

Of course random.shuffle( x) is the intended way to effect a
permutation uniformly at random.

[Paul Rubin]

Boris Borcic <bb*****@gmail. comwrites:

x.sort(cmp = lambda x,y : cmp(random.rand om(),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.

[Boris Borcic]

Paul Rubin wrote:

Boris Borcic <bb*****@gmail. comwrites:

>x.sort(cmp = lambda x,y : cmp(random.rand om(),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"

[Boris Borcic]

Thanks for these details. BB

Tim Peters wrote:

[ Boris Borcic]

>x.sort(cmp = lambda x,y : cmp(random.rand om(),0.5))

pick a random shuffle of x with uniform distribution ?

Say len(x) == N. With Python's current sort, the conjecture is true
if and only if N <= 2.

>Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort,

No idea what that could mean in a rigorous, algorithm-independent way.

>I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?

If a list is already sorted, or reverse-sorted, the minimum number of
comparisons needed to determine that is N-1, and Python's current sort
achieves that. It first looks for the longest ascending or descending
run. If comparison outcomes are random, it will decide "yes, already
sorted" with probability 1/2**(N-1), and likewise for reverse-sorted.
When N 2, those are larger than the "correct" probabilities 1/(N!).
So., e.g., when N=3, the sort will leave the list alone 1/4th of the
time (and will reverse the list in-place another 1/4th). That makes
the identity and reversal permutations much more likely than "they
should be", and the bias is worse as N increases.

Of course random.shuffle( x) is the intended way to effect a
permutation uniformly at random.

[Boris Borcic]

Boris Borcic wrote:

Paul Rubin wrote:

>Boris Borcic <bb*****@gmail. comwrites:

>>x.sort(cmp = lambda x,y : cmp(random.rand om(),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"

[Boris Borcic]

Boris Borcic wrote:

Paul Rubin wrote:

>Boris Borcic <bb*****@gmail. comwrites:

>>x.sort(cmp = lambda x,y : cmp(random.rand om(),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) provideonly
partial information; iow the algorithm knows for example x<=y and needsto
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".