-1

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.

  • 2
    If you don't have any comparison function you can't make correct decisions about which element to merge first – Daenyth Nov 3 '15 at 18:53
  • Can you assume that the ordering between lists is the same? (I.e. you know there is a consistent ordering, you just don't know what it is) If that's the case you can reconstruct a partial ordering from common elements, and then merge according to that. – Ordous Nov 3 '15 at 19:06
  • @Ordous Unfortunately not - all I can say is that they will 'usually' be the same. As someone pointed out below, a heuristic/best guess approach is the best that can be done there. I do have all the lists in advance, so I could make a percentage based partial ordering (to put a number value to 'usually'). – The Bearded Templar Nov 3 '15 at 19:07
  • 3
    The problem with this question is that we have no idea what you consider to be "reasonable" and "unreasonable". Is "concatenate the lists" unreasonable? Why or why not? – Eric Lippert Nov 3 '15 at 19:11
  • That's a fair criticism. I'm not sure how much more rigorous this is, but what I'm looking for is a resulting list where an element a is before an element b if a is before b in most other lists where they both appear. From the comments in the previous answer, I think I'm going to have to go with a probability based approach. – The Bearded Templar Nov 3 '15 at 19:28
5

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

graph of example

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.

  • Does this work if the input ordering is imperfect? Op mentioned that the inputs are usually in the same order, implying that sometimes A>B and sometimes B>A – Daenyth Nov 3 '15 at 19:40
  • If that's the case, it would cause a cycle while constructing the graph. You would just detect the cycle and disallow that edge. You could choose the winner first-come-first-served or based on some other heuristic. – Karl Bielefeldt Nov 3 '15 at 19:47
  • This looks possibly related: math.stackexchange.com/questions/199144/… – Daenyth Nov 3 '15 at 20:09
1

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.

  • In the example you posted that makes sense. Those lists have nothing in common, so you have to just sort of pick something. In my case the lists will likely have things in common. So I guess it's more like we have an approximate comparison function or a learning comparison function. i.e. from list 1 we know that 'Task A' probably comes before 'Task B' so next time we encounter Task B, we put it after Task A in the sorted list. – The Bearded Templar Nov 3 '15 at 18:57
  • That's not a general solution. A type either has an no order, partial order, or total order. Be definition, if it has no order, then an ordered list is an impossibility. Partial order means that you can compare some instances against each other, but you can't compare any two arbitrary instances. Total order means you can have an order between any two instances no matter what they are. It sounds like you're looking for a way to derive a partial order from an example set of data. – Daenyth Nov 3 '15 at 19:00
  • @TheBeardedTemplar: So, you do have an equality-comparison operator available, to tell when two elements are the same, but not an inequality-comparison that tells you the order, right? – Bart van Ingen Schenau Nov 3 '15 at 19:01
  • That is more of a heuristic and I really don't think it's going to help you much. It's not a general solution, and is going to be computationally complex. Is there no way you can derive order information from outside sources and implement a comparison for this type? – Daenyth Nov 3 '15 at 19:01
  • A heuristic is kind of what I'm going for. As you've pointed out, this doesn't have a general solution. I don't have to account for edge cases or people trying to break it. From the data I could probably derive a partial order (for example, a is less than b if a comes before b in more than 50% of lists in which they both appear). – The Bearded Templar Nov 3 '15 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.