[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: Paul Rubin <"http://phr.cx" () NOSPAM ! invalid>
Date: 2005-10-27 9:09:11
Message-ID: 7x64rjs4w8.fsf () ruckus ! brouhaha ! com
[Download RAW message or body]
Lasse Vågsæther Karlsen <lasse@vkarlsen.no> 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.
--
http://mail.python.org/mailman/listinfo/python-list
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic