亞最大尺寸的給定約束

Question

我整數數組的數組列表如下 -

27 14 62 
15 92 15 
16 40 90 
61 23 78 
23 70 90 
25 93 98 

我想找到的最大尺寸的所有子集，使得

a1[0]<a2[0] && a1[1]<a2[1] && a1[2] <a2[2] 

我did- 1）我按照升序對arraylist的每一行進行排序。 2）然後我排序利用比較 整個數組列表所以我得到這個 -

14 27 62 
15 85 92 
16 40 90 
23 61 78 
23 70 90 
25 93 98 

但現在，我堅持。我不確定如何根據上述約束找到所有最大尺寸的子集。 例如在上述情況下， -

14 27 62 
15 85 92 
25 93 98 

14 27 62  
23 61 78 
25 93 98 

14 27 62 
23 70 90 
25 93 98 

是最大尺寸子集可能的。

Answer 1

考慮這個算法：

1. 對於每個row，開始跟蹤subset
2. 對於隨後的每個row2
   1. 如果row < row2，然後加入到子集，並從步驟2遞歸地繼續
3. 比較subset大小與任何先前保存的子集：
   1. 如果較大，則刪除所有以前保存的子集，並保存這一個
   2. 如果相等，則該子集添加到先前保存的子集的列表

雖然這種算法的時間複雜度是指數，這也很容易實現，並且可以受用較小的數據集。

List<List<int[]>> findMaximumSubsets(int[][] arr) { 
    List<List<int[]>> acc = new ArrayList<>(); 
    for (int i = 0; i < arr.length - 1; i++) { 
     findMaximumSubsets(arr, i, acc, new ArrayList<>(Collections.singletonList(arr[i]))); 
    } 
    return acc; 
} 

void findMaximumSubsets(int[][] arr, int row, List<List<int[]>> acc, List<int[]> current) { 
    for (int i = row + 1; i < arr.length; i++) { 
     if (comparator.compare(arr[row], arr[i]) < 0) { 
      // ... (not spoiling for you ...) 
     } 
    } 
} 

Comparator<int[]> comparator = new Comparator<int[]>() { 
    @Override 
    public int compare(int[] a1, int[] a2) { 
     int cmp1 = Integer.compare(a1[0], a2[0]); 
     if (cmp1 > -1) { 
      return 0; 
     } 
     int cmp2 = Integer.compare(a1[1], a2[1]); 
     if (cmp2 > -1) { 
      return 0; 
     } 
     return Integer.compare(a1[2], a2[2]); 
    } 
}; 

Answer 2

是否真的允許在檢查約束之前對各個數組進行排序？以下算法應該以任何方式工作。

以下算法應爲O工作（N ）找到一個最大的集（你需要的一切。在這種情況下，最壞的情況下努力是指數）：

1. 建立一個向無環圖其中各個陣列是節點，並且當且僅當b可以根據約束遵循a時，節點a和b之間存在邊。
2. 對此圖進行拓撲排序。
3. 按排序順序（從「最小」節點開始）遍歷節點，併爲每個節點x計算具有x作爲「最大」節點的最大子集。這可以通過查看所有以前的節點來完成y：用包含x的子集進行初始化，然後對於所有y：如果x可以跟隨y將x添加到爲y計算的最大子集，如果該子集大於先前x的子集記得它最大。
4. 在線性通過所有節點時找到總體最大的子集。

實施例：

14 27 62 
15 85 92 
16 40 90 
23 61 78 
23 70 90 
25 93 98 

已經在拓撲順序。因此，我們通過線計算行：

14 27 62 -> 14 27 62 
15 85 92 -> 14 27 62, 15 85 92 
16 40 90 -> 14 27 62, 16 40 90 
23 61 78 -> 14 27 62, 23 61 78 
23 70 90 -> 14 27 62, 23 70 90 
25 93 98 -> 14 27 62, 15 85 92, 25 93 98