Given a series of statements such as:a<ca<bb<c(Read as a is before b, a is before c, etc.)  What is the order of the elements?  In this example, the answer is a<b<c.A less trivial question would be:a<c<db<dc<ea<bThis one has four answers: a<b<c<d<e, a<c<b<d<e, a<b<c<e<d, a<c<b<e<d.Edit: To be clear, an algorithm need only return 1 of the possible answers for the logical statements.  There will also never be a case where the statements have a contradiction.  E.g. below is an impossible input:a<bb<a
What algorithm can be used to determine order given incomplete information?
algorithms;sorting;logic
A topological sort algorithm can sort a collection of data according to some set of rules as you have specified, where not all pairs have a pre-defined ordering.Typically the rules only define a partial ordering, so there are multiple possible orderings and topological sorting chooses an arbitrary one. If there's a contradiction in the rules you have specified, there will be no possible ordering.If you can give a true/false/don't-know answer for any pair of elements in constant time, IIRC there are sequential algorithms that topologically sort in linear time - O(Vertices + Edges), as mentioned in comments below.A contradiction in the constraints arises if, and only if, there is a cycle in the constraints. It may therefore by useful to identify the greatest strongly connected components in the digraph of constraints.It may also be useful to grow your initial seed set of constraints to include all possible constraints that can be proven directly or indirectly from that seed set. In general, the resulting set is considered closed with respect to the function used to find new members, so algorithms that grow sets like this are closure algorithms - not to be confused with a lexical-scope closure. Particular set closures often mentioned WRT abstract algebra include symmetric closures (if a?b is in your set, also add b?a), reflexive closures (if a?b is in your set, also add a?a and b?b) and transitive closures (if a?b and b?c are in your set, also add a?c).Ordering relations are transitive - if a<b and b<c then a<c - so the transitive closure of your set of constraints may be useful.You might also want to identify clusters of elements that are ordered with respect to each other (assuming no contradiction) without caring initially about the order. This defines a partitioning of the elements into equivalence classes, given an in-the-same-cluster sense of equivalence. For that, you could use a disjoint set / union-find data structure - the equivalence classes are disjoint from each other, so each equivalence class is a set that's disjoint from the others. The union operation from union find basically says whatever classes these two elements are in, combine those classes into a single class if necessary. The find determines which class a particular element is in, usually by choosing one element to represent that class.A common theme in all this is the theory of graphs, although aspects come from abstract algebra and elsewhere. Basically, the relation a<b can be modelled as an edge on a graph between vertices representing the elements a and b. If you care about the ordering, that's a directed graph.For example a relation x<y will appear in the transitive closure of your initial set of constraints if both x and y are in the same strongly connected component of the digraph.Sorry, I got confused above - the relation x<y will appear in the transitive closure if there's any path between x and y in the digraph, but that doesn't imply a strongly connected component. A strongly connected component requires a cycle, not just a path.