0

I got a list of elements, like [C, D, B, A] (every letter is a tuple of RGB color) and a list of rules (first element > second elements): [(D,C), (D,B), (D,A), (C,B), (C,A), (B,A)], so D has to be sorted after C, B and A (so comes last), C comes after B and A, (placing it 3rd), etc.

Correct order is [A, B, C, D]:

for _ in colors:
    color += [_]
for element in rules:
    listtwo += [(element)]
        
for x in listtwo:
    if x[0] in color:
        color.remove(x[0])
    if x[1] in color:
        color.remove(x[1])

for elements in rules:
    if elements[0] == elements[1]:
        pass
    else:
        listone += [elements]
        for el in listone:
            pos_a = colors.index(el[0])
            pos_b = colors.index(el[1])
            if pos_a > pos_b:
                colors.remove(el[0])
                colors.insert(posizione_b, el[0])

if len(color) > 0:
    colors.remove(colors[0])
colors.reverse()
if len(color) > 0:
    colors.append(colors[0])

It works in some specific cases but not in general (And the code is not well written). Any ideas?

Further examples, it works with:

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))
]

Output is:

[(255, 0, 0), (0, 255, 0), (0, 0, 255), (0, 255, 255), (255, 255, 0)]

It doesn't works with this example:

colors = [
    (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), (222, 190, 134), (191, 52, 233)
]

rules = [
    ((79, 247, 87), (250, 150, 227)),
    ((250, 150, 227), (149, 198, 219)),
    ((79, 247, 87), (149, 198, 219)),
    ((79, 247, 87), (133, 228, 115)),
    ((149, 198, 219), (133, 228, 115)),
    ((133, 228, 115), (142, 150, 92)),
    ((250, 150, 227), (142, 150, 92)),
    ((79, 247, 87), (142, 150, 92)),
    ((197, 223, 252), (142, 150, 92)),
    ((197, 223, 252), (250, 150, 227)),
    ((121, 154, 210), (79, 247, 87)),
    ((121, 154, 210), (197, 223, 252)),
    ((121, 154, 210), (142, 150, 92)),
    ((127, 219, 167), (121, 154, 210)),
    ((197, 223, 252), (79, 247, 87)),
    ((127, 219, 167), (79, 247, 87)),
    ((127, 219, 167), (142, 150, 92)),
    ((121, 154, 210), (104, 132, 238)),
    ((104, 132, 238), (197, 223, 252)),
    ((127, 219, 167), (197, 223, 252)),
    ((222, 190, 134), (121, 154, 210)),
    ((191, 52, 233), (121, 154, 210)),
    ((222, 190, 134), (191, 52, 233)),
    ((191, 52, 233), (127, 219, 167)),
    ((191, 52, 233), (222, 190, 134))

]

Wrong output:

[(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), (222, 190, 134), (191, 52, 233)]

Correct Output:

[(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)]
5
  • 2
    Please tell us where your code works and where it doesn´t so we can help you better. Nov 24, 2020 at 10:49
  • Can you give an example of colorsand when your code doesn't work. Nov 24, 2020 at 10:50
  • Did you mean to revert the sort order here? D is smaller than C if it comes first in the correct sorted output.
    – Martijn Pieters
    Nov 24, 2020 at 11:14
  • Your letters-only example and your concrete examples are directly contradicting one another. Your correct output for the larger colors list has (142, 150, 92) appear first, while it is listed in the rules as coming after other colors, where your small letters-only example has D come first, which fits if we interpret any (a, b) pair in the rules as meaning a comes before b.
    – Martijn Pieters
    Nov 24, 2020 at 11:29
  • 1
    When I put your rules in a graph, you can see there is a circular dependency in them.
    – Martijn Pieters
    Nov 24, 2020 at 12:13

2 Answers 2

2

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:

directed graph representation of the rules

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:

specific example as directed 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.

14
  • @superbrain: brain fog. I cleared up that section.
    – Martijn Pieters
    Nov 24, 2020 at 12:19
  • 1
    Try rules = [(1, 2), (2, 3)] and colors = [2, 3, 1]. You incorrectly produce [2, 3, 1], and this time it's the fault of the algorithm. Nov 24, 2020 at 12:40
  • @superbrain: I'd say it's the fault of the question with no clarity on what kind of sort they really need ;-)
    – Martijn Pieters
    Nov 24, 2020 at 13:05
  • 1
    Well, at least the title says "Order list of some elements by list of rules", not "Order and filter list of some elements by list of rules". Nov 24, 2020 at 13:40
  • 1
    Not sure what you mean with "unreachable nodes". Unreachable from where? It's not like we have some root. But with what I guess you meant, you still don't have to state how to handle it. You can if you want to, but you can also be happy enough with any valid order. Nov 24, 2020 at 14:18
2

You can use graphlib.TopologicalSorter introduced in Python 3.9:

ts = TopologicalSorter()
for color in colors:
    ts.add(color)
for rule in rules:
    ts.add(*rule)
ordered = list(ts.static_order())

However, with your rules, this leads to an error

graphlib.CycleError: ('nodes are in a cycle', [(191, 52, 233), (222, 190, 134), (191, 52, 233)])

That's what Martijn pointed out as well.

But if you remove the incorrect rule, then it gives you the expected result.

Demo:

from graphlib import TopologicalSorter

colors = [(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), (222, 190, 134), (191, 52, 233)]
rules = [((79, 247, 87), (250, 150, 227)), ((250, 150, 227), (149, 198, 219)), ((79, 247, 87), (149, 198, 219)), ((79, 247, 87), (133, 228, 115)), ((149, 198, 219), (133, 228, 115)), ((133, 228, 115), (142, 150, 92)), ((250, 150, 227), (142, 150, 92)), ((79, 247, 87), (142, 150, 92)), ((197, 223, 252), (142, 150, 92)), ((197, 223, 252), (250, 150, 227)), ((121, 154, 210), (79, 247, 87)), ((121, 154, 210), (197, 223, 252)), ((121, 154, 210), (142, 150, 92)), ((127, 219, 167), (121, 154, 210)), ((197, 223, 252), (79, 247, 87)), ((127, 219, 167), (79, 247, 87)), ((127, 219, 167), (142, 150, 92)), ((121, 154, 210), (104, 132, 238)), ((104, 132, 238), (197, 223, 252)), ((127, 219, 167), (197, 223, 252)), ((222, 190, 134), (121, 154, 210)), ((191, 52, 233), (121, 154, 210)), ((222, 190, 134), (191, 52, 233)), ((191, 52, 233), (127, 219, 167)), ((191, 52, 233), (222, 190, 134))]
expect = [(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)]

rules.remove(((191, 52, 233), (222, 190, 134)))

ts = TopologicalSorter()
for color in colors:
    ts.add(color)
for rule in rules:
    ts.add(*rule)
ordered = list(ts.static_order())

print(ordered)
print(ordered == expect)

Output:

[(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)]
True

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.