here is a competitive programming question:

[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!

• Seems like you need to count the number of linear (or total) orders on the set $\{1,\dots,N\}$ that contain a given partial order on $\{1,\dots,N\}$. See mathoverflow.net/q/45875/7252 for discussion. – András Salamon Nov 16 '13 at 13:49

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.