Maintain the same sort order using different comparisons

Suppose we have an object that can be sorted using two or more comparison functions. For example, Box

which has length

a width

and a height

. We can sort the block array according to any of these fields.

Now let's look at two arrays of objects Box

that contain the same fields. In the first array, the fields are sorted in ascending order by their size length

. In the second array, the fields are sorted in order of increasing size by theirs 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 theirs length

or theirs height

, we will have the same sort order.

Is it just a matter of finding the longest common subsequence of boxes between two sorted arrays? Is there a better way to do this, or a good C ++ implementation without having to implement an algorithm for LCS if that's the most practical way? Are there any data structures that support this property by themselves?

+3


source to share


1 answer


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

Intuitively, you can think of this as a matryoshka problem . The only elements that satisfy the ratio should fit perfectly into each other, but using the square of their longest edge instead of the roth topology.



There are two related questions here, plus a canned C ++ implementation .

+4


source







All Articles