Partially Ordered Sort

An algorithm to sort a collection by a sequence of comparators.

Comparators

A comparator takes two elements a and b and returns

`0` - if they are equal
a positive number if `a > b`
a negative number if `a < b`

For example the natural comparator on the integers is

def small_first(a, b):
    return a - b

The Python sorted function takes a comparator function as a keyword input

>>> sorted([1, 5, 2, 4, 3], cmp=small_first)
[1, 2, 3, 4, 5]

We may choose to sort by different criteria. For example we might choose to prefer even numbers

def evens_first(a, b):
    return a%2 - b%2

>>> sorted([1, 5, 2, 4, 3], cmp=evens_first)
[4, 2, 5, 1, 3]

Note in the example above that all of even numbers precede all of the odd numbers; evens_first is satisfied. Also note that there are several possible solutions. In this case there are 12 possible solutions that all satisfy the comparator function. sorted returns one at random.

posort

To obtain the solution [2, 4, 1, 3, 5] where numbers are sorted first by evenness and then by magnitude we can use the function posort.

The posort function attempts to satisfy a sequence of comparator functions of decreasing precedence.

>>> posort([1, 5, 2, 4, 3], evens_first, small_first)
[2, 4, 1, 3, 5]

The rule for even numbers dominates the rule for small numbers. Any number of comparator functions can be specified.

Equivalent structures

A comparator function completely specifies a partial order.

A comparator function can describe any directed acyclic graph (DAG)

Author

Matthew Rocklin

License

New BSD license. See LICENSE.txt

History

This idea was originally developed for the Theano project