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
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.
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
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.
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.
@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.