Sorting with only a partial order definition

[Bryan Olson]

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