CODEWITHSUNDEEP
c++algorithm
mcorley
mcorley

Reputation: 767

Maintain the same sorted order using different comparisons

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?

Upvotes: 3

Views: 166

Answers (1)

MrGomez
MrGomez

Reputation: 23886

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++.

Upvotes: 4

Related Questions