440,772 Members | 961 Online
Need help? Post your question and get tips & solutions from a community of 440,772 IT Pros & Developers. It's quick & easy.

# Sorting with only a partial order definition

 P: n/a 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. In other words, if I pick two random items from the list I may or may not have a rule that dictates the order of those two items. The rule could be "implicit" in that I got rules for other items, for instance: [a, b, c, d] a < b b < c If I now pick a and c out of the list I would not know wether a or c comes first, unless I grab the rules for a
7 Replies

 P: n/a 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 Oct 27 '05 #2

 P: n/a Lasse Vågsæther Karlsen writes: 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. In other words, if I pick two random items from the list I may or may not have a rule that dictates the order of those two items. The rule could be "implicit" in that I got rules for other items, for instance: That's called topological sorting and any reference on graph algorithms will describe how to do it. I don't know of Python code offhand but it's easy to write. http://en.wikipedia.org/wiki/Topological_sorting gives a straightforward linear-time algorithm. Oct 27 '05 #3

 P: n/a Paul Rubin wrote: Lasse Vågsæther Karlsen writes:I have a list of items and a "rule" for ordering them.Unfortunately, the rule is not complete so it won't define the correctorder for any two items in that list.In other words, if I pick two random items from the list I may or maynot have a rule that dictates the order of those two items. The rulecould be "implicit" in that I got rules for other items, for instance: That's called topological sorting and any reference on graph algorithms will describe how to do it. I don't know of Python code offhand but it's easy to write. http://en.wikipedia.org/wiki/Topological_sorting gives a straightforward linear-time algorithm. Thank you both. -- Lasse Vågsæther Karlsen http://usinglvkblog.blogspot.com/ mailto:la***@vkarlsen.no PGP KeyID: 0x2A42A1C2 Oct 27 '05 #4

 P: n/a Bryan Olson wrote: The usual tools to deal with partial orderings are directed acyclic graphs, and "topological sorting". Try Googling the terms along with "Python". here's a rather powerful timbot implementation: http://mail.python.org/pipermail/pyt...ly/006625.html Oct 27 '05 #5