Consider the specific ranking 4, 8, 1, 2, 7, l0, 9, 5, 3, 6 of the 10 objects of the example. It is easy to determine whether or not this ranking violates any constraints of the partial order by checking each one. Since this ranking violates two of the nine constraints, 6 ?/FONT> 8 and 7 ?/FONT> 1, it is not a topological sort. Any ranking may be checked in this way. This leads to an obvious algorithm based on the generation of all rankings of the n objects.
A search-based algorithm:
If a ranking is found which violates no constraints, then the ranking is a topological sort, print it and stop. If all possible rankings have been tried and no topological sort found, then print out the message that none exists, and stop.
To implement this algorithm in a programming language requires finding a way to generate the rankings so that all the distinct rankings are eventually generated. The procedure permutations of Chapter 4 does this. Any implementation of the algorithm could take time proportional at least to the number of distinct rankings of n objects. A particular ranking can be constructed by selecting any one of the n objects to be first in the ranking, then selecting any one of the remaining n - 1 objects to be second in the ranking, and so on. Thus there are n ?/FONT> (n - 1) ?/FONT> (n - 2) ?/FONT> ?/FONT> ?/FONT> ?/FONT> ?/FONT> 2 ?/FONT> 1 distinct rankings of n objects. This product is n factorial. Consequently this solution can deal with values of n no greater than 16.* For larger n, an algorithm must be found that need not consider all rankings.
* See Section 1.8.2.