Merging Sorted Lists (with no comparison function)

Question

I have a few lists of items (which will likely but not necessarily have common elements). The lists are known to be sorted, but don't have a comparison function (they were manually put into the system in sorted order). I'd like to combine these lists into one list containing all the elements that is in a reasonable order given the existing ones.

Obviously there are edge cases and decisions to be made - I'm not too worried about the specifics, but rather I'd like a general approach to tackle the problem. Obviously if the two lists have nothing in common, there isn't much to be done besides appending one to the other, but that won't happen much.

As an example:

l1 = ['Task A', 'Task B', 'Task C', 'Task D']
l2 = ['Task B', 'Task B2', 'Task D', 'Task G']
l3 = ['Task A', 'Task C', 'Task E', 'Task D']
result = ['Task A', 'Task B', 'Task B2', 'Task C', 'Task E', 'Task D', 'Task G']

Again, I realize there is no perfect solution, and the output is not mission critical, I just want it to be reasonably nicely ordered in most cases. Any help would be appreciated.

Answer 1

This is a well-defined problem with a deterministic solution. You can think of each list as forming part of a directed acyclic graph:

Then, constructing a merged order is simply a matter of using one of the well-known algorithms to find a topological sorting. The more similarities you have between the lists, the fewer valid topological sorts you will have. If there are no elements in common, the topological sort will work for that case as well. It will list all possible ways to combine the three lists. You just have to pick the one that suits you best aesthetically.

Answer 2

If you have literally no comparison function, then the only sane option is to pick the same order each time:

one = [1,2,3]
two = [4,5,6]
three = [7,8,9]

merge(one, two, three) == [1,4,7,2,5,8,3,6,9]

---

If there is some order, and the items can be compared for equality, but you can't encode the ordering explicitly, you can track how many times you've seen them in certain orders and use that to generate heuristics.

You can build up a history to base guesses on by storing all visits

I think these data types and algebra (expressed in pseudo-scala) would serve this purpose well.

// How many times a given item has been seen
type ItemCount = Map[Item, Int]

// NB ItemHistory forms a commutative monoid with zero as empty maps and mappend adding the counts together
case class ItemHistory(itemsSeenBefore: ItemCount, itemsSeenAfter: ItemCount)

// Fold over a list of input items and generate history for each one, storing the count of all items seen before and after
List[Item] => Map[Item, ItemHistory]

// Update your counts with more data
(Map[Item, ItemHistory], List[Item) => Map[Item, ItemHistory]

// Generate an ordering between two items, with a % accuracy.
// Whichever has been seen more often before or after defines the ordering.
// The accuracy is determined by taking the ratio of times that ordering was correct vs the entire history.
(Item, ItemHistory) => (Item, ItemHistory) => (Ordering, Float)

// Apply some cutoff for filtering out inaccurate orderings
(Ordering, Float) => Ordering

If you implement a class with methods along those lines, you can use it to generate heuristics. Because the ItemHistory is a monoid, you can easily train it offline with the data you have today, persist the ItemHistories in whatever way is convenient, and then continually update them with new training data as it comes in.