Task Dependency/Combinatorics

Question

here is a competitive programming question:

You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For convenience, we assume the tasks are numbered from 1 to 4. Suppose that task 4 depends on both task 2 and task 3, and task 2 depends on task 1. One possible sequence in which we can complete the given tasks is [3,1,2,4] - in this sequence, no task is attempted before any of the other tasks that it depends on. The sequence [3,2,1,4] would not be allowed because task 2 depends on task 1 but task 2 is scheduled before task 1. In this example, you can check that there exactly three possible sequences compatible with the dependencies: [3,1,2,4], [1,2,3,4] and [1,3,2,4]. In each of the cases below, you have N tasks numbered 1 to N with some dependencies between the tasks. You have to calculate the number of ways you can reorder all N tasks into a sequence that does not violate any dependencies.

[Task, Dependency(s)] : [1, NA], [2,1], [3,2], [4,1], [5,4], [6, 3 and 5], [7,6], [8,7], [9,6], [10, 8 and 9].

I inferred the following:

• Any sequence will always start with 1, since it has no dependencies.
• 6 will always be in the 6th position of any sequence.
• 10 will always be at the last position.

Then, by trial and error, and listing all possibilities for the two separate parts of the sequence (1 _ _ _ _ 6 and 6 _ _ _ 10), I got 6x3 = 18 possibilities. However, for a larger set of data, these deductions would not be easy. What is the way to calculate this logically and find the number of possibilities, and how can this be integrated into a program?

(I have tried to represent the question as clearly as possible, but you can visit this link to view the question (Q. No 4): http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf)

I am a high school student preparing for a programming competition, and I haven't taken many courses on algorithm design, so this might be a trivial question - please excuse me!

Answer 1

It is a good question, certainly not trivial.

This problem is essentially counting the number of topological orderings. A topological ordering/sort is basically a valid ordering of completing the tasks in a dependency graph.

According to the link that @AndrásSalamon put into his comment, it is #P-complete: this means it is very hard to actually compute for a large number of tasks and dependencies.

They are expecting you to write a program that does it for just the small number of tasks that they give you. You probably need to do brute-force; i.e. try all possible orders, check if it is valid, and count them.

Alternatively, some smart variation of brute force, such as enumerating all possible topological orderings, and counting them.

Frequently this is the type of question asked by a competition:

• An impossibly difficult question if extended to large input size,
• Therefore, some sort of brute-force must be used,
• But a smart variation of brute-force,
• That can depend on the specific characteristics and limitations of the input they give you; if you don't take advantage of these limitations, and/or if you don't figure out the variation they want you to do, then your program will over-run its time limits.

You can also take a look at On Computing the Number of Topological Orderings of a Directed Acyclic Graph. To run this, you would make a dependency graph of the input tasks, then count the topological orderings using the algorithm(s) in this paper. I am not sure if this would finish in time on the input data you have; but one way to know would be to try it.