What are some ways to combine a number of (potentially incompatible) sorted sub-sets of a total set into a (partial) ordering of the total set? [closed]

Question

I have a sorting problem that I'm pretty sure doesn't have a canonical "answer" - but probably has a number of different approaches, each with pros/cons. I'm interested in hearing some different approaches.

Suppose a bunch of people {p_i | i=1,...,M} are ranking their favorite ice cream flavors. In total there are N different flavors, but a single person p_i only ranks the n_i << N flavors that he or she is most familiar with. I'm interested in combining these sub-rankings into a plausible overall ranking of all N flavors.

For a concrete situation: my M and N are both roughly 1000 (by coincidence), and each n_i is about 20. You can assume there's enough overlap in the flavors people rank such that no flavor is completely "isolated".

Again, I'm interested in hearing different ways to approach this, even if there isn't a single clear answer. Thanks!

Answer 1

One way to approach this problem would be to construct a directed a cyclic graph representing all of the constraints on the ordering of the elements. The nodes in the graph would represent the different elements to be compared and you would have an edge from a first node a second node if someone had ranked the first element has better than the second element. This graph would not be too large and can be constructed in linear time by creating one node for every. object and then adding edges based on the preferences.

There are two possibilities for this graph. First, if the graph contains a cycle, there must be a conflict in the preferences and there's no way to order the elements consistently. Second, if the graph has no cycles, then any topological ordering of the graph will give an overall consistent ordering of the elements, since every element will be placed after all elements that transitively come before it.

Hope this helps!