Noober Noober - 4 months ago 14
Java Question

subsets of maximum size in java given a constraint

I have a arraylist of integer array as follows-

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


I want to find all the subsets of maximum size such that

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


What I did-
1) I sorted each row of the arraylist in ascending order.
2) Then I sorted the entire arraylist using comparator
So I get this-

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


But now, I am stuck. I am not sure how to find all the subsets of maximum size subject to the above mentioned constraint.
For example in the above case,-

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


are the maximum size subsets possible.

Answer

Consider this algorithm:

  1. For each row, start tracking a subset
  2. For each subsequent row2
    1. If row < row2, then add to the subset, and recursively continue from step 2
  3. Compare the size of subset with any previously saved subset:
    1. If greater, then delete all previously saved subsets, and save this one
    2. If equal, then add this subset to the list of previously saved subsets

Although the time complexity of this algorithm is exponential, it's fairly easy to implement, and may be good enough for smaller datasets.

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]);
    }
};