CODEWITHSUNDEEP
algorithm
rookie
rookie

Reputation: 2923

Merging sorted lists without comparison key

Say we have the following lists:

list 1: x, y, z
list 2: w, x
list 3: u

And we want to merge them such that the order among each individual list is respected. A solution for the above problem might be w, x, y, z, u.

This problem is easy if we have a comparison key (e.g. string comparison; a < z), as this gives us a reference to any element's position relative to other elements in the combined list. But what about the case when we don't have a key? For the above problem, we could restate the problem as follows: 

x < y AND y < z AND w < x where x, y, z, w, u are in {0, 1, 2, 3, 4}

The way I'm currently solving this type of problem is to model the problem as a constraint satisfaction problem -- I run the AC3 arc consistency algorithm to eliminate inconsistent values, and then run a recursive backtracking algorithm to make the assignments. This works fine, but it seems like overkill.

Is there a general algorithm or simpler approach to confront this type of problem?

Upvotes: 2

Views: 53

Answers (1)

Timothy Shields
Timothy Shields

Reputation: 79531

  1. Construct a graph with a node for every letter in your lists.

    x    y    z


w    u

  2. Add a directed edge from letter X to letter Y for every pair of consecutive letters in any list.

    x -> y -> z
^
|
w    u

  3. Topologically sort the graph nodes to obtain a final list that satisfies all your constraints.

    If there were ever a cycle in your graph, the topological sorting algorithm would detect that cycle, revealing a contradiction in the constraints induced by your original lists.

Upvotes: 1

Related Questions