Solving the Task Ordering problem in Python

By John Lekberg on August 01, 2020.


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.

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

  1. Task D
  2. Task E
  3. Task B
  4. Task C
  5. Task A

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"},
    "B": {"C"},
    "D": {"E"},
}

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


def task_order_bf(*, tasks, constraints):
    """Solve the 'Task Ordering' problem using brute force.
    
    tasks -- a set of tasks.
    constraints -- a dictionary that maps each task to
        all the tasks that must come after.
    """
    for candidate in permutations(tasks):
        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"},
    "B": {"C"},
    "D": {"E"},
}

task_order_bf(tasks=tasks, constraints=constraints)
('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 ... )

That Task before is allowed to be before Task after.

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

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


def task_order_fast(*, tasks, constraints):
    """Solve the 'Task Ordering' problem quickly, using
    Khan's Algorithm for topological sorting.
    
    tasks -- a set of tasks.
    constraints -- a dictionary that maps each task to
        all the tasks that must come after.
    """
    return khans_algorithm(V=tasks, E=constraints)


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)

    def link(tail, head):
        """Add the edge (tail, head) to e_out and e_in."""
        e_out[tail].add(head)
        e_in[head].add(tail)

    def unlink(tail, head):
        """Remove the edge (tail, head) from e_out and e_in."""
        e_out[tail].remove(head)
        e_in[head].remove(tail)

    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:
        for head in E[tail]:
            link(tail, head)

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

    while len(S) > 0:
        tail = S.pop()
        L.append(tail)
        for head in tuple(e_out[tail]):
            unlink(tail, head)
            if source(head):
                S.add(head)

    # 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"},
    "B": {"C"},
    "D": {"E"},
}

task_order_fast(tasks=tasks, constraints=constraints)
['D', 'B', 'E', 'C', 'A']

For more information about Khan's algorithm, read these documents:

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

O(|V| + |E|)

For n tasks and m constraints,

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.

As it is, the functions return None when a solution is not found.

Your goal is to modify the code to, instead of returning None, raise an Exception that describes that constraints that are in conflict. E.g.

ERROR: Unable to order tasks. Tasks "A", "D", "E" form a cycle.

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!

::...
免责声明:
当前网页内容, 由 大妈 ZoomQuiet 使用工具: ScrapBook :: Firefox Extension 从互联网中抓取并分享;
内容版权归原作者所有;
本人对内容的有效性/合法性不承担任何强制性责任.
若有不妥, 欢迎评注提醒:

蟒营®编程思维提高班 Python版/第11期 正在报名

精品小班/ 每期<42人


扫描报名: 101camp12py

蟒营®式 原创课程

伴你重享学习乐趣

官网: py.101.camp

Reactivate Joy by Self-teching with You


任何问题可先进入知识星球(免费)咨询:
FAQ

关注公众号, 持续获得相关各种咨询:
mainium


追问

任何问题, 随时邮件提问可也:
askdama@googlegroups.com


...::