I have an ArrayList<ArrayList<int[]>>, which has an undefined number of int[].
Example input (note that text "= Condition 0/1/2" is not part of the ArrayList).
= Condition 0
[2, 6], [3, 7]
= Condition 1
[1, 3], [2, 4], [2, 3]
= Condition 2
[1, 2]
(PART A) I wish to create all possible permutations of all the int[] pairs (ArrayList<int[]> option = new ArrayList<>();, line 9), provided there is only one pair from each condition, e.g. first from C0, second from
[2,6], [1,3], [1,2]
[2,6], [2,4], [1,2]
[2,6], [2,3], [1,2]
[3,7], [1,3], [1,2]
and so on...
(PART B) Once I have all possible permutations (2^numOfConditions), I combine each value from ArrayList<int[]> pairs and put all integers into a Set to make sure I only get unique numbers. Eventually, I return the shortest set (i.e., the one that has the biggest number of repeating ints).
public static Set<Integer> findOptimalPairs(ArrayList<ArrayList<int[]>> conditions) {
// A
ArrayList<ArrayList<int[]>> listOfConditions = new ArrayList<>();
for (int i = 0; i < conditions.get(0).size(); i++) {
for (int j = 0; j < conditions.get(1).size(); j++) {
for (int k = 0; k < conditions.get(2).size(); k++) {
ArrayList<int[]> option = new ArrayList<>();
option.add(conditions.get(0).get(i));
option.add(conditions.get(1).get(j));
option.add(conditions.get(2).get(k));
listOfConditions.add(option);
}
}
}
//A
//B
Set<Integer> best = new HashSet<>();
for (ArrayList<int[]> pairs : listOfConditions) {
Set<Integer> curr = new HashSet<>();
for (int[] pair : pairs) {
for (int num : pair) curr.add(num);
}
best = (best.size() > 0 && best.size() <= curr.size()) ? best : curr;
}
return best;
//B
}
PART B works just fine, but how can I modify A, so it will be able to go through conditions' sizes that are different from 3? I hardcoded the values (0,1,2) for now, because I have no idea how to modify it for larger collections.
Have spent so much time on this already, and I feel like the answer is not particularly difficult.
Java 11, if that matters. Thank you.
how can I modify A, so it will be able to go through conditions' sizes that are different from 3? I hardcoded the values (0,1,2) for now, because I have no idea how to modify it for larger collections.
Basically you create a 1D array that will hold at each index the number of int[] arrays for that set.
Then you create an additional 1D array of the same size and you "count" using the stored sizes to know when to reset each counter. If you've ever counted in other bases you should know exactly what I mean, except we are treating the left side as the least significant digit.
For instance, with your data set of:
[2, 6], [3, 7]
[1, 3], [2, 4], [2, 3]
[1, 2]
There are three rows, so you'd make an array of size three and store the number of items in each set.
Here I'm hard-coding just to show the process. In the actual code it will be dynamic based on the data passed in:
int[] setSize = {2, 3, 1};
Now we start off a new array of the same size, with all values at zero (which is the default anyways):
int[] counters= {0, 0, 0}
Starting from the left, we increment the value in that index until we reach "set size". Whenever we hit "set size" we reset that index back to zero and increment the column to the right (following the same rule for each column of resetting and incrementing to the right).
These would be the sequences generated:
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 2, 0]
[1, 2, 0]
The numbers represent what index from the int[] array you should pick from each set in that combination. So then we just translate those indices to the corresponding int[] array from the input data set.
This approach is ITERATIVE, requiring no recursion.
Here's what that code might look like:
import java.util.*;
import java.util.ArrayList;
class Main {
public static void main(String[] args) {
ArrayList<ArrayList<int[]>> conditions = new ArrayList<ArrayList<int[]>>();
ArrayList<int[]> condition1 = new ArrayList<int[]>();
condition1.add(new int[] {2,6});
condition1.add(new int[] {3,7});
conditions.add(condition1);
ArrayList<int[]> condition2 = new ArrayList<int[]>();
condition2.add(new int[] {1,3});
condition2.add(new int[] {2,4});
condition2.add(new int[] {2,3});
conditions.add(condition2);
ArrayList<int[]> condition3 = new ArrayList<int[]>();
condition3.add(new int[] {1,2});
conditions.add(condition3);
System.out.println("Input Data:");
display(conditions);
System.out.println();
ArrayList<ArrayList<int[]>> combos = findOptimalPairs(conditions);
System.out.println("Output Data:");
display(combos);
}
public static void display(ArrayList<ArrayList<int[]>> data) {
for(ArrayList<int[]> set : data) {
for(int i=0; i<set.size(); i++) {
System.out.print(Arrays.toString(set.get(i)));
if (i<(set.size()-1)) {
System.out.print(", ");
}
}
System.out.println();
}
}
public static ArrayList<ArrayList<int[]>> findOptimalPairs(ArrayList<ArrayList<int[]>> conditions) {
ArrayList<ArrayList<int[]>> combos = new ArrayList<ArrayList<int[]>>();
int combinations = 1;
int[] setSize = new int[conditions.size()];
for(int i=0; i<conditions.size(); i++) {
ArrayList<int[]> set = conditions.get(i);
int size = set.size();
setSize[i] = size;
combinations = combinations * size;
}
int[] counters = new int[setSize.length];
for(int i=0; i<combinations; i++) {
ArrayList<int[]> combo = new ArrayList<int[]>();
for(int j=0; j<counters.length; j++) {
combo.add(conditions.get(j).get(counters[j]));
}
combos.add(combo);
for(int j=0; j<counters.length; j++) {
if (counters[j]<(setSize[j]-1)) {
counters[j]++;
break;
}
else {
counters[j] = 0;
}
}
}
return combos;
}
}
Output generated:
Input Data:
[2, 6], [3, 7]
[1, 3], [2, 4], [2, 3]
[1, 2]
Output Data:
[2, 6], [1, 3], [1, 2]
[3, 7], [1, 3], [1, 2]
[2, 6], [2, 4], [1, 2]
[3, 7], [2, 4], [1, 2]
[2, 6], [2, 3], [1, 2]
[3, 7], [2, 3], [1, 2]