Find all combinations in arraylist recursively

Question

I completely lost it. I can do it iteratively, but recursion is new to me. If I am provided with an arraist with 1, 2, 3 inside it, then the total possible combos with repetitions will be 27.

111, 112, 113, 121, 122, 123, etc.

how can i find this recursively? I would show my code, but I'm not even close to getting the concept ...

Answer 1

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

Answer 2

Here is the hard-coded solution 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 combinations of functions (). This function takes the original array as a parameter and a second array to track indexes.

When I call a function to run it, I initialized this array of indices for all 0.

For each function on the stack, you must increase the indices in the index array to get the correct output. Notice how in my solution I use three if statements, this is the hard-coded part. This can probably be done using a for loop.

Finally, the function function combination () is called again inside itself (recursion) with a modified array of indices until the end sentence is fulfilled (the first index has the maximum output).

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

Answer 3

Here is the 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 add a character to line b from arraylist a and call itself recursively. As soon as the length of the string b reaches 3 (i.e. the size of the arraylist a), this means that the combo is generated and this is displayed. This method is generalized to any arbitrary size.

Answer 4

What about a solution that doesn't care if you resized 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 helps a bit at first.

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

This is a 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]] 

Answer 5

I understand your struggle. Solving problems recursively is often difficult when you need to keep track of all the challenges and decide how to navigate this problem. With a little thought, I was able to solve this problem using an int array to represent permutations and an ArrayList for storage. Loops and repetition checks were not used.

I wrote one easy-to-invoke method called getPermutations, which allows you to find all permutations of length n with integers [1, n]. This method calls the actual recursive method, which is a bit more complicated. When solving such a problem, it is important to track certain data points using the arguments of the method , however this makes the method a little painful for the actual call (therefore, using 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 recursion works:

• start with a completely “vague” permutation: you need to find all possible values ​​at every possible index

• at current index i, recursively recalls a method to capture each value, val, from 1 to n

• a complete permutation was found when i == n (i.e. each index was defined 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) in index i is taken into account, so the collection can be returned (at which the point will continue to increment i and move horizontally)

Answer 6

Bit late for this party, and sorry, this is in C #, but hey, this is like Java. Everything here seems a bit complicated, so here's a pretty simple function that is 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 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; }