使用不同的比較維護相同的排序順序

Question

假設我們有一個可以使用兩個或多個比較函數進行排序的對象。例如具有length，width和height的Box。我們可以根據這些字段中的任何一個字段對數組進行排序。

現在考慮兩個包含相同框的Box對象數組。在第一個數組中，這些盒子按照它們的length的大小順序排列。在第二個數組中，這些盒子按照它們的height的大小順序排列。很可能這兩個排序的數組將按不同的順序列出這些框。

我們希望找到第三個數組，其中包含這些框的子集，並且如果我們按其length或height對它們進行排序，則我們將具有相同的排序順序。

這是簡單的找到兩個排序數組之間最長的公共子序列的問題嗎？有沒有更好的方法來做到這一點或在C++中的一個很好的實現，而不必實現LCS的算法，如果這是最實際的方法呢？有沒有任何數據結構可以保持這個屬性的實用性？

Answer 1

你剛剛描述的是longest common subsequence problem的一個實例，它是NP-hard。

直觀上，您可以將其視爲matryoshka嵌套問題。滿足關係的唯一元素必須完全適合彼此，但使用其最長邊的平方而不是死記錄拓撲。

這裏有兩個relatedquestions,加a canned implementation in C++。