Noober - 2 months ago 8x
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.

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