Below is some code I wrote recently to calculate the different combinations of elements in an Array. It is a simplified and straightforward recursive solution.
A recursive solution has 2 important piecies: a base case, and a recursive step. Here is an example of how the code below executes:
given: [1,2,3,4]
Recursive Step - Iterate through each element and break it out, leaving the rest of the elements
(first iteration)
1 [2,3,4]
2 [1,3,4]
3 [1,2,4]
4 [1,2,3]
(second iteration)
1 2 [3,4]
1 3 [2,4]
1 4 [2,3]
…. etc
The recursive step is defined in plain english as just remove a value, then call the function again on the rest of the list (with this element removed).
In the base case, once we have an array the size of length 1, we just simply return the array - so simple!
There is a key piece of code that, given an element and an array of arrays, prepends the element to each array. i.e.
1, [[5,6], [7,8], [3,4]] –> [ [1,5,6], [1,7,8], [1,3,4] ]
Pretty simple.
import java.util.ArrayList;
public class Combination {
public ArrayList<ArrayList<Object>> compute(ArrayList<Object> restOfVals) {
if(restOfVals.size() < 2) {
ArrayList<ArrayList<Object>> c = new ArrayList<ArrayList<Object>>();
c.add(restOfVals);
return c;
}
else {
ArrayList<ArrayList<Object>> newList = new ArrayList<ArrayList<Object>>();
for(Object o: restOfVals) {
//make a copy of the array
ArrayList<Object> rest = new ArrayList<Object>(restOfVals);
//remove the object
rest.remove(o);
newList.addAll(prependToEach(o, compute(rest)));
}
return newList;
}
}
private ArrayList<ArrayList<Object>> prependToEach(Object v, ArrayList<ArrayList<Object>> vals){
for(ArrayList<Object> o : vals) {
o.add(0, v);
}
return vals;
}
public static void main(String args[]) {
ArrayList<Object> i = new ArrayList<Object>();
i.add("1");
i.add("2");
i.add("3");
i.add("4");
Combination c = new Combination();
ArrayList<ArrayList<Object>> ff = new ArrayList<ArrayList<Object>>();
ff = c.compute(i);
System.out.println(ff.size());
System.out.println(ff);
}
}
