kj wrote: > Challenge: to come up with a sorting task that cannot be achieved > by passing to the sort method (or sorted function) suitable values > for its key and reverse parameters, but instead *require* giving > a value to its cmp parameter. > > For example, > > from random import random > scrambled = some_list.sort(cmp=lambda x, y: cmp(random(), 0.5))
The above violates the transitivity requirement as stated below. The result will have a bias. > can be achieved (to a very good approximation at least) with > > scrambled = some_list.sort(key=lambda x: random()) > > Is there a real-life sorting task that requires (or is far more > efficient with) cmp and can't be easily achieved with key and > reverse? The core developers don't think there is one. list.sort() no longer supports the cmp parameter in 3.x. > Many thanks in advance, > > G. > > P.S. I guess that, if sort is going to produce a non-trivial, > *consistent* order, a function CMP passed as the value of its cmp > parameter must satisfy the following properties: > > 0. CMP(x, y) must be non-zero for some elements x, y of the list; > 1. anti-symmetry: sign(CMP(x, y)) must be equal to -sign(CMP(y, x)); > 2. transitivity: if sign(CMP(x, y)) equals sign(CMP(y, z)), then > sign(CMP(x, z)) must be equal to sign(CMP(x, y)). > > In (1) and (2), sign() stands for the function > > -1 if x < 0 > sign(x) = 0 if x == 0 > 1 if x > 0 > > I suppose that all bets are off if these properties are not satisfied, > though the documentation does not make this entirely clear, as far > as I can tell. (If I'm wrong about this alleged omission, please > point me to the part of the docs that I missed.) -- http://mail.python.org/mailman/listinfo/python-list
