All task orderings

[Script Coder]

Hey all, I am stuck and in need of an algorithm that will solve this problem:

Given N tasks (numbered 1-N) and a series of task restrictions (do task 3 before task 2) print out all possible task orderings.
Example input:

3
3 2

Explanation: there are 3 tasks and task 3 must be done before task 2 (each restriction will have its own line)
Example output:

1 3 2
3 1 2
3 2 1

[Smac89]

Is there more than one restriction? And can there be more than 2 restricted tasks i.e. can you have "2 3 4" as a restriction?

This seems like an implementation problem, but I have a feeling it is more brute-force

An idea:

Example
Given the value 6 { 1, 2, 3, 4, 5, 6}
Given restriction 4 5 3
for each permutation of "1 2 6"

1, 2, 6, 4, 5, 3(swap 4, 6)
1, 2, 4, 6, 5, 3(swap 4, 2)
1, 4, 2, 6, 5, 3(swap 4, 1)
4, 1, 2, 6, 5, 3(swap 5, 6)
4, 1, 2, 5, 6, 3(swap 5, 2)
4, 1, 5, 2, 6, 3(swap 5, 1)
4, 5, 1, 2, 6, 3(swap 3, 6)
4, 5, 1, 2, 3, 6(swap 3, 2)
4, 5, 1, 3, 2, 6(swap 3, 1)
4, 5, 3, 1, 2, 6
....

As you can see, through out the swaps, 1, 2, 6 maintain their positions i.e. 1 before 2 before 6
and 4 5 3 maintain theirs as well: 4 before 5 before 6

Using this method of getting permutation of non restricted values you can print all possible orderings. This eventually turned out to be a brute-force problem

[Script Coder]

Smac89 wrote:

Is there more than one restriction?

Yes, there is definitely more than one restriction.

Smac89 wrote:

And can there be more than 2 restricted tasks i.e. can you have "2 3 4" as a restriction?

If you mean that task two must be done before tasks 3 and 4 then yes, however it is represented as follows:

2 3
2 4

this is also possible:

2 3
4 3

meaning that task 3 must be done after tasks 2 and 4.

I have a feeling it is more brute-force

While a brute force solution will always work, when you have N being >100 000 and M >1000 (where M is the number of restrictions), one needs a more efficient approach.

[Smac89]

No matter how effiecient the algorithm you finally settle on will be, it will still have to print the same values. So I guess what you really need is an algorithm for printing permutations of a certain range of number without printing the same permutation twice

Also you will need to find a way of storing the values that are restricted in such a way that they are in the order the restrictions keep them in.

The number of things to print is equal to (length of restricted * length of non-restricted)+1

[Script Coder]

I might have a solution:
Store a list of orderings and then permute through the orderings, like so:
Restrictions:

1 2
2 5
4 3

[ [1,2,5], [4,3] ]

and then permute the following items:

[1,1,1,2,2]

and then at each permutation you remove one of the elements from the specific group.
The only problem I cannot then solve is if you have got the following list:

[ [ [1,4], 3], [2,5] ]

Any ideas?
Also thank you for all your help thus far.

[JLBorges]

Start with the topsort algorithm http://en.wikipedia.org/wiki/Topological_sorting

Then extend it to recursively generate all the possible topological orderings.

[Smac89]

0.o @JLBorges is on the right track here. Take a look at definition of topological sort:

In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

[Script Coder]

@JLBorges That is a very good idea, only which of the two algorithms described in the wiki article would be best suited? I would lean towards the second due to the fact that it is recursive. Also would you please give a little advice on how to perform your extension.

[JLBorges]

> which of the two algorithms described in the wiki article would be best suited?

Kahn's algorithm (the first one) would be easier to extend.


> Also would you please give a little advice on how to perform your extension.

http://www.google.com/search?q=Knuth+Szwarcfiter+algorithm

Their original paper turns up as one of the first few search results:
http://www.cs.ncl.ac.uk/publications/trs/papers/61.pdf

[Script Coder]

Thanks you, I am going to have to translate the out-dated code, but it looks promising. I will (literally) keep you posted.