3

Suppose we have an object that can be sorted using two or more comparison functions. For instance a Box that has a length, a width, and a height. We can sort an array of boxes according to any of these fields.

Now consider two arrays of Box objects that contain identical boxes. In the first array the boxes are sorted in order of increasing size by their length. In the second array the boxes are sorted in order of increasing size by their height. Most likely these two sorted arrays will list the boxes in a different order.

We want to find a third array that has a subset of the boxes and has the property that if we sort them by either their length or their height, we will have the same sorted order.

Is this simply a matter of finding the longest common subsequence of boxes between the two sorted arrays? Is there a better way to do this or a nice implementation in C++ without having to implement the algorithm for LCS if that is the most practical way to go? Are there any data structures that maintain this property on their own that are practical?

mcorley
  • 767
  • 12
  • 21
  • It's a matter of finding *a* common subsequence; it's only a matter of finding the *longest* common subsequence if you decide that it is. (Also, you have to decide how you want to handle the case that two boxes have the same height but different lengths, or vice versa.) – ruakh Mar 17 '12 at 23:22
  • Those the subset of Boxes need to be optimal (e.g. the longest subset possible)? – pmr Mar 17 '12 at 23:23
  • Yes my first thought is that it is a matter of finding a common subsequence, and the subset of boxes needs to be optimal, so it would be the longest common subsequence. – mcorley Mar 18 '12 at 00:18

1 Answers1

4

What you've just described is an instance of the longest common subsequence problem, which is NP-hard.

Intuitively, you can view this as a matryoshka nesting problem. The only elements that satisfy the relation must perfectly fit inside one another, but using the square of their longest edge instead of rote topology.

Here's two related questions, plus a canned implementation in C++.

Community
  • 1
  • 1
MrGomez
  • 23,788
  • 45
  • 72