Find all combinations in arraylist recursively

You can use this concept and make your own recursive function. using that you can get all possible combinations.

How about a solution that wouldn't care if you changed the size of the ArrayList?

public static void main(String args[]) { ArrayList<Integer> ali = new ArrayList<>(); ali.add(1); ali.add(2); ali.add(3); System.out.println(combinations(ali).toString().replace("], [", "],\n [")); } 

This is just a little help at the start.

public static List<List<Integer>> combinations(List<Integer> input) { return step(input, input.size(), new ArrayList<>()); } 

This is the recursive method,

public static List<List<Integer>> step(List<Integer> input, int k, List<List<Integer>> result) { // We're done if (k == 0) { return result; } // Start with [[1], [2], [3]] in result if (result.size() == 0) { for (Integer i : input) { ArrayList<Integer> subList = new ArrayList<>(); subList.add(i); result.add(subList); } // Around we go again. return step(input, k - 1, result); } // Cross result with input. Taking us to 2 entries per sub list. Then 3. Then... List<List<Integer>> newResult = new ArrayList<>(); for (List<Integer> subList : result) { for(Integer i : input) { List<Integer> newSubList = new ArrayList<>(); newSubList.addAll(subList); newSubList.add(i); newResult.add(newSubList); } } // Around we go again. return step(input, k - 1, newResult); } 

Outputs:

[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 3, 1], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 3, 1], [2, 3, 2], [2, 3, 3], [3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 3, 1], [3, 3, 2], [3, 3, 3]] 

Here is a hard coded solution that I just made in python, but it should demonstrate the principle:

def combinations(original,indexes): indexes[2] = indexes[2] + 1 if(indexes[2] == 3): indexes[1] = indexes[1] + 1 indexes[2] = 0 if(indexes[1] == 3): indexes[0] = indexes[0] + 1 indexes[1] = 0 if(indexes[0] != 3): print str(original[indexes[0]]) + str(original[indexes[1]]) \ + str(original[indexes[2]]) combinations(original, indexes) combinations([1,2,3],[0,0,0]) 

Notice how I have the function combinations(). This function takes the original array as a parameter, and a second array for tracking indexes.

When I call the function to start it off, I initialized that indexes array to all 0s.

At each function in the stack, you should increase the indexes in the indexes array to produce the correct output. Note how in my solution I use three if statements, this is the hard coded part. This could probably be done with a for loop.

Lastly, the function the combinations() function is called again inside of itself (recursion) with the modified index array until the end clause is met (first index is has maxed out).

This code snippet should serve as a guide as I see you tagged java

Here is a method in java:

String combine(ArrayList<Integer> a, String b){ String c=""; if(b.length()==a.size()){ System.out.println(b); //found a combo return ""; } //append characters to string b for(int x=0;x<a.size();x++){ c=b+((Integer)a.get(x)).intValue(); c+=combine(a,c); } return c; } 

In each iteration of the loop, it will append a character to string b from arraylist a and call itself recursively. Once the length of string b reaches 3 (i.e. size of arraylist a), it means a combo is generated and this is displayed. This method is generalized for arraylist of any size.

I understand your struggle. Solving problems recursively can often be tricky when it comes to keeping track of all of the calls and deciding how to navigate the problem. After a bit of thought, I was able to solve this problem, using an int array to represent permutations and an ArrayList for storage. No Loops were used, nor checks for repeats.

I wrote one easy-to-invoke method called getPermutations that allows you to find all of the permutations of length n with integers [1,n]. This method calls on the actual recursive method, which is a bit more complex. When solving a problem like this, it is important to keep track of certain data points using arguments of the method, however this makes the method a bit painful to actually invoke (hence the use of a helper method). My code is shown below.

//Recursive Method public static ArrayList<int[]> permutationsFrom(int[] start,int i, int val, ArrayList<int[]> prev) { int n = start.length; if (i == n) { final int[] perm = start.clone(); prev.add(perm); return prev; } else if (val > n) { return prev; } else { int[] next = start.clone(); next[i] = val; prev.addAll(permutationsFrom(next, i+1, 1, new ArrayList<int[]>())); return permutationsFrom(next, i, ++val, prev); } } //Invokation public static ArrayList<int[]> getPermutations(int n) { return permutationsFrom(new int[n], 0, 1, new ArrayList<int[]>()); } //Print the results public static void main(String[] args) { ArrayList<int[]> perms = getPermutations(3); System.out.println(perms.size()); for (int[] perm : perms) { for (int el : perm) { System.out.print(el + " "); } System.out.println(); } } 

How the recursion works:

• start with a completely "undetermined" permutation: every possible value at every possible index needs to be found

• at the current index, i, recursively recall the method to capture every value, val, from 1 to n

• a complete permutation has been found when i == n (i.e. every index has been determined from 0 to n-1), and therefore the int array should be added to the collection of previous permutations, prev

• if val > n every possible value (from 1 to n) at index i has been accounted for, so the collection can be returned (at which the point the method will continue to increment i and move horizontally)

Bit late to this party, & sorry, it's in c#, but hey, it's similar to Java. Everything here seems a bit complicated, so here's a function which is pretty simple, which should be easy to translate to Java -

 public static List<List<T>> Permutations<T>(List<T> list) { List<List<T>> result = new List<List<T>>(); for (int i = 0; i < list.Count(); i++) { T initialValue = list[i]; List<T> clonedList = list.Where((item, index) => { return index != i; }).ToList(); // proper copy, less the initialValue item // here's where the recursion happens, but only if there are at least 2 items left in the list List<List<T>> permutations = clonedList.Count > 0 ? Permutations(clonedList) : new List<List<T>> { new List<T>() }; foreach (List<T> permutation in permutations) { List<T> combined = new List<T> { initialValue }; combined.AddRange(permutation); result.Add(combined); } } return result; }