# Solving the Task Ordering problem in Python

By John Lekberg on August 01, 2020.

NOTE: Michal Porteš found a mistake with my code. I didn't define the dict `constraints` correctly. I have fixed this. Thanks, Michal!

This week's blog post is about solving the "Task Ordering" problem in Python. You will learn:

# Problem statement

You have a list of tasks that you need to complete. E.g.

• Task A - do the dishes.
• Task D - go for a run.
• Task E - have dinner.

But you can't complete the tasks randomly. You have some constraints. E.g.

Your goal is to find a way to complete the tasks in order and not violate the constraints. E.g. one solution is

# How I represent the data in the problem

I represent the list of tasks as a set. E.g.

``````{ "A", "B", "C", "D", "E" }
``````

I represent the constraints as a dictionary that maps each task to the set of tasks that must come after. E.g. this constraint dictionary

``````{
"E": {"A"},
"D": {"B", "C", "E"},
"B": {"C"},
}
``````

represents these constraints:

I represent the solution as a sequence of tasks. E.g.

``````("D", "E", "B", "C", "A")
``````

# Creating a brute force solution

A simple way to use brute force to solve this problem is to generate every permutation of tasks and check if it satisfies the constraints. Here's a Python function, `task_order_bf`, that does this:

``````from itertools import permutations, combinations

"""Solve the 'Task Ordering' problem using brute force.

constraints -- a dictionary that maps each task to
all the tasks that must come after.
"""
good = all(
before not in constraints[after]
for before, after in combinations(candidate, 2)
if after in constraints
)
if good:
return candidate

tasks = {"A", "B", "C", "D", "E"}
constraints = {
"E": {"A"},
"D": {"B", "C", "E"},
"B": {"C"},
}

``````
``````('D', 'E', 'A', 'B', 'C')
``````

This code generates all possible orders of the tasks (ignoring constraints) using itertools.permutations.

This code checks each candidate by using the built-in function all and itertools.combinations to make sure that for every pair of elements

( ... before ... after ... )

What's the time complexity of this solution? For n tasks:

• There are n! permutations of the n tasks.
• Checking that a permutation satisfies the constraints takes O(n2) operations.

As a result, the overall time complexity of this function is

O(n! n2)

# Creating a more efficient solution

This problem of "Task Ordering" is also known also "Topological Sorting". The concepts of "tasks" and "constraints" map to vertices and edges of a directed graph.

For a directed graph with vertices V and edges E, Khan's Algorithm performs a topological sort in

O(|V| + |E|) steps

Here's a Python function, `task_order_fast`, that solves the "Task Ordering" problem using Khan's Algorithm:

``````from collections import defaultdict

"""Solve the 'Task Ordering' problem quickly, using
Khan's Algorithm for topological sorting.

constraints -- a dictionary that maps each task to
all the tasks that must come after.
"""

def khans_algorithm(*, V, E):
"""Use Khan's Algorithm to generate a topological sort
of a directed graph given by vertices V and edges E.

Time complexity is O(|V| + |E|).

V -- set. Vertices.
E -- dict. Map vertex to set of outgoing vertices.
"""

# Set up auxiliary data structures and functions.

e_out = defaultdict(set)
e_in = defaultdict(set)

"""Remove the edge (tail, head) from e_out and e_in."""

indegree = lambda v: len(e_in[v])
outdegree = lambda v: len(e_out[v])

# "source" refers to "source vertex".
source = lambda v: indegree(v) == 0

# Khan's Algorithm

for tail in E:

L = []
S = set(filter(source, V))

while len(S) > 0:
tail = S.pop()
L.append(tail)

# If cycles are present, then no solution exists.

no_cycles = all(
indegree(v) == 0 and outdegree(v) == 0 for v in V
)
if no_cycles:
return L

tasks = {"A", "B", "C", "D", "E"}
constraints = {
"E": {"A"},
"D": {"B", "C", "E"},
"B": {"C"},
}

``````
``````['D', 'B', 'E', 'C', 'A']
``````

What's the time complexity of this algorithm? Khan's algorithm is

O(|V| + |E|)

For n tasks and m constraints,

• There are n vertices in V.
• There are m edges in E.

As a result, the overall time complexity for this function is

O(n + m)

# In conclusion...

In this week's post, you learned how to solve the "Task Ordering" problem using brute force. Then you learned how to recast the problem in terms of topological sorting. This allowed you to use Khan's algorithm to create a faster solution to the "Task Ordering" problem.

Topological sorting is useful for dependency resolution in build systems (like GNU Make) and package managers (like npm).

In a mathematical sense, topological sorting is like creating a linear extension from a partial order to a total order.

My challenge to you:

A solution can't exist if the task constraints form a cycle. E.g.