[prev in list] [next in list] [prev in thread] [next in thread] 

List:       python-list
Subject:    Re: Sorting with only a partial order definition
From:       Bryan Olson <fakeaddress () nowhere ! org>
Date:       2005-10-27 9:07:42
Message-ID: yN08f.7237$7h7.6636 () newssvr21 ! news ! prodigy ! com
[Download RAW message or body]

Lasse Vågsæther Karlsen wrote:
 > I have a list of items and a "rule" for ordering them.
 >
 > Unfortunately, the rule is not complete so it won't define the correct
 > order for any two items in that list.

This is called a "partial ordering".

[...]
 > If there isn't anything built in, does anyone have an idea about how to
 > go about creating such an ordering function ? Tweaking a cmp-like
 > function to return 0 for "undefined" didn't seem to work so there must
 > be a slightly more intelligent solution than that. Perhaps the rules
 > would have to be checked in a specific order.

The usual tools to deal with partial orderings are directed acyclic graphs,
and "topological sorting".  Try Googling the terms along with "Python".


-- 
--Bryan
-- 
http://mail.python.org/mailman/listinfo/python-list

[prev in list] [next in list] [prev in thread] [next in thread]