sort(cmp=func)

David Wahler dwahler at gmail.com
Thu Jul 10 06:13:31 CEST 2008


On Wed, Jul 9, 2008 at 10:58 PM, Daniel Fetchinson
<fetchinson at googlemail.com> wrote:
>
> > I have a list of objects that generate code.  Some
> > of them depend on others being listed first, to
> > satisfy dependencies of others.
> >
> > I wrote a cmp function something like this:
> >
> > def dep_cmp(ob1, ob2):
> >
> >       if ob1.name in ob2.deps:
> >               return -1
> >       else:
> >               return 1
> >
> > I also tried returning 0 when there were no dependency
> > relationships between the objects.
> >
> > This failed, because every object was not compared with
> > ever other.  I imagine that this is because sort assumes
> > that if a > b and b > c, then a > c.  In my case, this
> > isn't really true.  If a is not dependent on b, and
> > b is not dependent on c, that doesn't mean that a is not
> > dependent on c.
> >
> > Is there a better way?
>
> It's only meaningful to talk about sorting if your particular
> definition of "<" is transitive. I.e. a < b and b < c should imply a <
> c. If this is not satisfied, it doesn't make sense to sort according
> to your "<" definition. It's just not a well-defined operation and no
> trick will make it work.
>

Presumably what the OP really wants is to sort using the transitive
closure of dep_cmp, which is a topological sort.

http://en.wikipedia.org/wiki/Topological_sorting has details and a
linear-time algorithm.

-- David



More information about the Python-list mailing list