You either have a total order or you could treat this a topological sort of a directed graph.
To treat this as a total order (requiring that there are rules for all nodes that produce a consistent order without ambiguities), you need to map your relative ordering rules to a total ordering of your inputs. You could use a comparison function for this, and then apply the functools.cmp_to_key()
utility function to make this a proper sort key:
from functools import cmp_to_key
comes_after = {('C', 'A'), ('B', 'A'), ('D', 'A'), ('C', 'B'), ('D', 'C'), ('D', 'B')}
@cmp_to_key
def ordering_rules(a, b):
if a == b: return 0
return 1 if (a, b) in comes_after else -1
sorted_colors = sorted(colors, key=ordering_rules)
I put your rules into a set, because membership testing against a set is much more efficient; (a, b)
is then a tuple that, if present in the comes_before
set indicates that a
should be sorted before b
, so a < b
is true and a == b
or a > b
is false.
Demo:
>>> colors = ['C', 'D', 'B', 'A']
>>> sorted(colors, key=ordering_rules)
['A', 'B', 'C', 'D']
The ordering_rules(a, b)
function acts like an old-fashioned cmp()
function, which would return a negative number if a < b
is true, 0 for when a == b
, and a positive number when a > b
is true.
The cmp_to_key()
decorator above just maps that implementations for the <
, <=
, ==
, >
and >=
operator hooks (__lt__
, etc.), so that normal sorting can compare any two elements without having to reference the above rules.
In fact, because the current implementation explicitly uses just <
comparisons to sort, you can make your own key object to achieve the same, just by giving it a __lt__
method.
For future-proofing, however, I'd also implement __eq__
for equality testing and then add the @functools.total_ordering
decorator to provide the hooks for the >
, >=
, etc.:
from functools import total_ordering
@total_ordering
class ColorSortKey:
comes_after = {('C', 'A'), ('B', 'A'), ('D', 'A'), ('C', 'B'), ('D', 'C'), ('D', 'B')}
__slots__ = ('color',)
def __init__(self, color):
self.color = color
def __lt__(self, other):
if not isinstance(other, ColorSortKey):
return NotImplemented
return (other.color, self.color) in self.comes_after
def __eq__(self, other):
if not isinstance(other, ColorSortKey):
return NotImplemented
return self.color == other.color
I gave the class a __slots__
attribute to help minimise memory use; you can sort very large lists with this class and still keep memory growth in check this way.
You can then use the above in much the same way, as a key
argument to list.sort()
or sorted()
:
>>> sorted(colors, key=ColorSortKey)
['A', 'B', 'C', 'D']
If your rules are variable, you could make the rules a parameter that you attach to the class via functools.partial()
, perhaps via classmethod for more self-documenting code:
from functools import partial, total_ordering
@total_ordering
class ColorSortKey:
__slots__ = ('color', 'comes_after')
@classmethod
def with_rules(cls, rules):
return partial(cls, set(rules))
def __init__(self, comes_after, color):
self.comes_after = comes_after
self.color = color
def __lt__(self, other):
if not isinstance(other, ColorSortKey):
return NotImplemented
return (other.color, self.color) in self.comes_after
def __eq__(self, other):
if not isinstance(other, ColorSortKey):
return NotImplemented
return self.color == other.color
This lets you use ColorSortKey.with_rules(rules)
as the sort key. Given your more expanded rules example:
>>> sorted(colors, key=ColorSortKey.with_rules(rules))
[(142, 150, 92), (133, 228, 115), (149, 198, 219), (250, 150, 227), (79, 247, 87), (197, 223, 252), (104, 132, 238), (121, 154, 210), (127, 219, 167), (191, 52, 233), (222, 190, 134)]
To sort the colors topologically, you treat your rules as edges in a directed graph.
To treat this as a topological sort, you could implement one of the algorithms that Wikipedia lists; I'm using Kahn's here:
from heapq import heapify, heappop, heappush
def topological_sort(colors, rules):
forward = {c: set() for c in colors}
reverse = {}
for a, b in rules:
if forward.keys() >= {a, b}: # a and be are both in the input list
forward[b].add(a)
reverse.setdefault(a, set()).add(b)
# determine what nodes have no incoming edges
# this is a set operation: any key in forward that's not a key in reverse
start = forward.keys() - reverse
# set up our queue, ensuring we process the next best node (lexicographical order)
queue = list(start)
heapify(queue)
result = []
while queue:
node = heappop(queue)
result.append(node)
for dep in forward.pop(node, ()):
reverse[dep].remove(node)
# only when there are more outgoing edges left
if not reverse[dep]:
heappush(queue, dep)
result += sorted(forward) # any remaining nodes with circular dependencies
return result
Note that we need to special-case the possibility of circular dependencies. Given your first full example, interpreting a rule (a, b)
as a comes before b, gives us:
>>> colors = [(255, 0, 0), (0, 255, 0), (0, 0, 255), (0, 255, 255), (255, 255, 0)]
>>> rules = [((0, 0, 255), (255, 0, 0)), ((0, 0, 255), (0, 255, 0)), ((0, 255, 0), (255, 0, 0)), ((255, 255, 0), (0, 0, 255)), ((255, 255, 0), (255, 0, 0)), ((255, 255, 0), (0, 255, 0)), ((0, 255, 255), (0, 0, 255)), ((0, 255, 255), (255, 0, 0)), ((0, 255, 255), (0, 255, 0)), ((255, 255, 0), (0, 255, 255))]
>>> topological_sort(colors, rules)
[(255, 255, 0), (0, 255, 255), (0, 0, 255), (0, 255, 0), (255, 0, 0)]
or reversing the dependencies:
>>> reversed_rules = [(b, a) for a, b in rules]
>>> topological_sort(colors, reversed_rules)
[(255, 0, 0), (0, 255, 0), (0, 0, 255), (0, 255, 255), (255, 255, 0)]
However, your final example is not free of circular dependencies. These are your rules, rendered as a directed graph:

If you look closely at these two rules:
(222, 190, 134) > (191, 52, 233)
(191, 52, 233) > (222, 190, 134)
you'll see that they lead back to one another. This is why your sort implementation failed here, either order is 'correct', in that there is no pure topological sort order possible here, and we need to add these remaining nodes at the end in arbitrary order (I picked lexicographical):
>>> topological_sort(colors, rules)
[(142, 150, 92), (133, 228, 115), (149, 198, 219), (250, 150, 227), (79, 247, 87), (197, 223, 252), (104, 132, 238), (121, 154, 210), (127, 219, 167), (191, 52, 233), (222, 190, 134)]
Neither of these colors could ever win, after all. In the above sorted result, that has led to an arbitrary ordering of (191, 52, 233), (222, 190, 134)
at the very end, and in your case the two values were reversed. That's not the sorting algorithms' fault, you gave it inconsistent rules, so there is no possibility of a proper total ordering.
Note that as of Python 3.9, you don't have to implement topological sorting yourself, as that version added graphlib.TopologicalSorter()
. This class makes it trivial to detect a circular dependency in your graph:
>>> from graphlib import TopologicalSorter
>>> sorter = TopologicalSorter(dict.fromkeys(colors, ()))
>>> used = set(colors)
>>> for a, b in rules:
... if used >= {a, b}:
... sorter.add(a, b)
...
>>> sorted_colors = list(sorter.static_order())
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/.../lib/python3.9/graphlib.py", line 241, in static_order
self.prepare()
File "/.../lib/python3.9/graphlib.py", line 103, in prepare
raise CycleError(f"nodes are in a cycle", cycle)
graphlib.CycleError: ('nodes are in a cycle', [(191, 52, 233), (222, 190, 134), (191, 52, 233)])
If you must try to get an order, even if arbitrary, you could use that class still but need to catch call TopologicalSorter.prepare()
directly, then pick off nodes that are ready have no predecessors, mark them as done as you process them:
from graphlib import TopologicalSorter, CycleError
def best_effort_topological_sort(colors, rules):
sorter = TopologicalSorter(dict.fromkeys(colors, ()))
used = set(colors)
for a, b in rules:
if used >= {a, b}:
sorter.add(a, b)
try:
sorter.prepare()
except CycleError:
pass
result = []
while sorter.is_active():
for node in sorter.get_ready():
used.remove(node)
result.append(node)
sorter.done(node)
if used:
# circular nodes, append in arbitrary order
result += sorted(used)
return result
which results in:
>>> best_effort_topological_sort(colors, rules)
[(142, 150, 92), (133, 228, 115), (149, 198, 219), (250, 150, 227), (79, 247, 87), (197, 223, 252), (104, 132, 238), (121, 154, 210), (127, 219, 167), (191, 52, 233), (222, 190, 134)]
You could play with how the remaining elements are added to the end of the result; you could sort them in lexicographical order, for example (result += sorted(used)
).
Note that the TopologicalSorter()
doesn't define an ordering for nodes at the same 'level', where they all have the same number of incoming nodes remaining. My topological_sort()
function uses a heap queue to process nodes in lexicographical order as you clear them from the graph, which can produce a different order from TopologicalSorter()
, which processes nodes in groups.
In practice, that means that my implementation will produce a stable order regardless of how colors
or rules
were initially ordered, whereas using TopologicalSorter()
can produce different results depending on how these were ordered at the start.
Take this example:
colors = [(73, 2, 121), (103, 226, 123), (24, 180, 171), (167, 17, 180), (76, 104, 15), (148, 77, 117)]
rules = [
((167, 17, 180), (76, 104, 15)),
((148, 77, 117), (103, 226, 123)),
((148, 77, 117), (73, 2, 121)),
((24, 180, 171), (76, 104, 15)),
((148, 77, 117), (167, 17, 180)),
((103, 226, 123), (24, 180, 171)),
((73, 2, 121), (24, 180, 171))
]
Represented as a graph:

There are two different paths through those rules:
>>> topological_sort(colors, rules)
[(76, 104, 15), (24, 180, 171), (73, 2, 121), (103, 226, 123), (167, 17, 180), (148, 77, 117)]
>>> best_effort_topological_sort(colors, rules)
[(76, 104, 15), (167, 17, 180), (24, 180, 171), (103, 226, 123), (73, 2, 121), (148, 77, 117)]
That's because, after clearing (76, 104, 15)
, there are 2 different colors that have no remaining dependencies in the rules, (167, 17, 180)
and (24, 180, 171)
. The TopologicalSorter()
class will return these in the relative order that we added them to the sorter, while my implementation picks the one lexicographically coming first, so (24, 180, 171)
.
Next, TopologicalSorter()
will process both those colors before looking for other colors that remain and now have 0 incoming rules, while my implementation has only removed (24, 180, 171)
from the queue before adding (73, 2, 121)
and (103, 226, 123)
to the queue, and so continues with (73, 2, 121)
next.
Both orderings are correct according to the rules, but if you were to shuffle the rules then best_effort_topological_sort()
can produce a different ordering again whereas my heapq-based implementation will always produce the same outcome.
colors
and when your code doesn't work.D
is smaller thanC
if it comes first in the correct sorted output.(142, 150, 92)
appear first, while it is listed in the rules as coming after other colors, where your small letters-only example hasD
come first, which fits if we interpret any(a, b)
pair in the rules as meaning a comes before b.