2

I'm trying to practice recursion, but for the life of me I can't figure out how to do this. Let's say I have 3 or more array lists inside of an array list, and I'd like to print out all possible combinations using recursion. How can I do that?

This is what I have so far

public static void main(String[] args) { ArrayList<ArrayList<String>> combList = new ArrayList<ArrayList<String>>(); ArrayList<String> fruitList = new ArrayList<String>(); ArrayList<String> lNameList = new ArrayList<String>(); ArrayList<String> locationList = new ArrayList<String>(); fruitList.add("Apple"); fruitList.add("Orange"); fruitList.add("Grape"); combList.add(fruitList); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); combList.add(colorList); numberList.add("One"); numberList.add("Two"); numberList.add("Three"); combList.add(numberList); combinations(combList, 0, 0, ""); } public static void combinations(ArrayList<ArrayList<String>> combList, int listIndex, int itemIndex, String result) { // Am I at the bottom of the y-axis? if(listIndex < combList.size()) { //Am I at the bottom of the x-axis? if(itemIndex < combList.size()) { ArrayList<String> curList = combList.get(listIndex); StringBuilder sb = new StringBuilder(); sb.append(result).append(curList.get(itemIndex)).append(" "); combinations(combList, listIndex + 1, itemIndex, sb.toString()); combinations(combList, listIndex, itemIndex + 1, result); } return; } System.out.println(result); return; }

I'm trying to get it to printout 

Apple Red One Apple Red Two Apple Red Three Apple Green One Apple Green Two Apple Green Three Apple Blue One Apple Blue Two Apple Blue Three Orange Red One Orange Red Two Orange Red Three Orange Green One . . . Grape Blue Three
Improve this question
4
  • One approach would be to iterate over the items in the first sublist, and recurse on the tail of the outer list, until there's one sublist left. Commented Oct 10, 2018 at 16:01
  • 1
    Not sure you're using recursion right. Think of it this way: you go down the recursion calls, and at each level remove one list from combList. Then at each level coming back up you take the result of the recursive call, and for every element from your result you append each element from the list you removed at that level. So at the bottom of your recursion you return ['One', 'Two', 'Three']. Next level up you return ['Red One', 'Red Two', 'Red Three' 'Green One', 'Green Two', 'Green Three', 'Blue One', ...] . Next level up you add the fruits. This will work for any number of lists. Commented Oct 10, 2018 at 16:20
  • @Alain Thanks Alain, I was able to figure it out thanks to you insight! How come the way I was trying before wasn't working, but this one did? It seems as if I was trying to do the same thing, just a bit reversed (Go down the lists first, then go inside)? Do you have any tips on how I should try to approach recursive problems like this? Commented Oct 10, 2018 at 16:49
  • @YitzakHernandez Most algorithm/programming textbooks will give you better explanations than I will, but if you want the one-liner (which won't apply in all cases) think of using the solution of a subproblem to resolve your problem. In your case the solution for one list is the original list. For 2 lists you take all elements of the second list and append them to the solution with one list. For 3 lists take all elements of the third list and append to the solution for 2 lists. And so on. I'll write done the java solution if I can find some time. Commented Oct 11, 2018 at 2:37

5 Answers 5

Reset to default
1

Main problem is that when you move to next list 

combinations(combList, listIndex + 1, itemIndex, sb.toString());

you allow iterating over it but only from position held by current itemIndex. This prevents you from iterating over its first elements. Solution would be using

combinations(combList, listIndex + 1, 0, sb.toString()); // ^--start iterating from first list item

Other problem is that you called curList.get(itemIndex) but earlier you tested 

if(itemIndex < combList.size()){ ... }

As you see you are comparing index from inner list with size of outer list. This will work only if both sizes are the same - if each inner list have same amount of elements as amount of inner lists. What you need is 

if(itemIndex < combList.get(listIndex).size()){ ... }

Next possible problem is fact that you are not handling empty inner lists. Lets say that you have [[a1,a2],[],[c1,c2]]. Because there are no elements in second inner lists your code will not let you move to next inner list since combinations(combList, listIndex, itemIndex + 1, result); is called in if(itemIndex < combList.get(listIndex).size()). To handle such case you can add else case like

if(itemIndex < combList.get(listIndex).size()) { //... } else if (combList.get(listIndex).isEmpty()){ combinations(combList, listIndex + 1, 0, result); }

So your method can look like: Demo

public static void main(String[] args) { List<List<String>> combList = new ArrayList<>(); combList.add(Arrays.asList("a1", "a2", "a3")); combList.add(Arrays.asList("b1", "b2")); combList.add(Arrays.asList()); combList.add(Arrays.asList("c1", "c2", "c3")); combinations(combList, 0, 0, ""); } public static void combinations(List<List<String>> combList, int listIndex, int itemIndex, String result) { // Am I at the bottom of the y-axis? if(listIndex < combList.size()) { //Am I at the bottom of the x-axis? if(itemIndex < combList.get(listIndex).size()) { List<String> curList = combList.get(listIndex); StringBuilder sb = new StringBuilder(); sb.append(result).append(curList.get(itemIndex)).append(" "); combinations(combList, listIndex + 1, 0, sb.toString()); combinations(combList, listIndex, itemIndex + 1, result); }else if (combList.get(listIndex).isEmpty()){ combinations(combList, listIndex + 1, 0, result); } return; } System.out.println(result); //return; - redundant as last instruction of method }

Output:

a1 b1 c1 a1 b1 c2 a1 b1 c3 a1 b2 c1 a1 b2 c2 a1 b2 c3 a2 b1 c1 a2 b1 c2 a2 b1 c3 a2 b2 c1 a2 b2 c2 a2 b2 c3 a3 b1 c1 a3 b1 c2 a3 b1 c3 a3 b2 c1 a3 b2 c2 a3 b2 c3
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

This could be done using Backtracking -

public class Main { static void back(List<List<Character>> res,String s,int idi) { if(s.length()==res.size()) { System.out.println(s); return; } for(int i=0; i<res.get(idi).size();i++) { s = s + res.get(idi).get(i); back(res,s,idi+1); s = s.substring(0,s.length()-1); } } public static void main(String[] args) { List<List<Character>> res = new ArrayList<List<Character>>(); Character a[]= new Character[] { 'A', 'B', 'C', 'D' }; List<Character> list1 = Arrays.asList(a); Character a2[]= new Character[] { 'E', 'F', 'G', 'H' }; List<Character> list2 = Arrays.asList(a); Character a3[]= new Character[] { 'I', 'J', 'K', 'L' }; List<Character> list3 = Arrays.asList(a); res.add(list1); res.add(list2); res.add(list3); back(res,"",0); } }

Output- AAA AAB AAC AAD ABA ABB ABC ABD ACA ACB ACC ACD ADA ADB ADC ADD BAA BAB BAC BAD BBA BBB BBC BBD BCA BCB BCC BCD BDA BDB BDC BDD CAA CAB CAC CAD CBA CBB CBC CBD CCA CCB CCC CCD CDA CDB CDC CDD DAA DAB DAC DAD DBA DBB DBC DBD DCA DCB DCC DCD DDA DDB DDC DDD

Improve this answer

Comments

0

We need to handle one more case in recursion 

 public static void main(String[] args) { ArrayList<ArrayList<String>> combList = new ArrayList<ArrayList<String>>(); ArrayList<String> fruitList = new ArrayList<String>(); ArrayList<String> colorList = new ArrayList<String>(); ArrayList<String> numberList = new ArrayList<String>(); fruitList.add("Apple"); fruitList.add("Orange"); fruitList.add("Grape"); combList.add(fruitList); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); combList.add(colorList); numberList.add("One"); numberList.add("Two"); numberList.add("Three"); combList.add(numberList); combinations(combList, 0, 0, ""); } public static void combinations(ArrayList<ArrayList<String>> combList, int listIndex, int itemIndex, String result) { ArrayList<String> curList; StringBuilder sb ; // Am I at the bottom of the y-axis? if(listIndex < combList.size()) { curList = combList.get(listIndex); //Am I at the bottom of the x-axis? if(itemIndex < curList.size()) { sb = new StringBuilder(); sb.append(result + curList.get(itemIndex) + " "); combinations(combList, listIndex + 1, 0, sb.toString()); combinations(combList, listIndex, itemIndex + 1, result); } else { combinations(combList, listIndex + 1, 0, result); } } System.out.println(result); return; }

Output:

Apple Red One Apple Red Two Apple Red Three Apple Red Apple Green One Apple Green Two Apple Green Three Apple Green Apple Blue One Apple Blue Two Apple Blue Three Apple Blue Apple One Apple Two Apple Three Apple Orange Red One Orange Red Two Orange Red Three Orange Red Orange Green One Orange Green Two Orange Green Three Orange Green Orange Blue One Orange Blue Two Orange Blue Three Orange Blue Orange One Orange Two Orange Three Orange Grape Red One Grape Red Two Grape Red Three Grape Red Grape Green One Grape Green Two Grape Green Three Grape Green Grape Blue One Grape Blue Two Grape Blue Three Grape Blue Grape One Grape Two Grape Three Grape Red One Red Two Red Three Red Green One Green Two Green Three Green Blue One Blue Two Blue Three Blue One Two Three
Improve this answer

1 Comment

Ah no, that was just me formatting my code for more simple variables and forgot to change that one.
0

My code. Order in the solution is reversed, but should be an easy fix if this is important. Also the recursive method returns a list of lists that needs to be turned into a String.

import java.util.ArrayList; import java.util.Arrays; public class Combinations { public static void main(String[] args) { ArrayList<ArrayList<String>> combList = new ArrayList<ArrayList<String>>(); ArrayList<String> fruitList = new ArrayList<String>(); ArrayList<String> colorList = new ArrayList<String>(); ArrayList<String> numberList = new ArrayList<String>(); fruitList.add("Apple"); fruitList.add("Orange"); fruitList.add("Grape"); combList.add(fruitList); colorList.add("Red"); colorList.add("Green"); colorList.add("Blue"); combList.add(colorList); numberList.add("One"); numberList.add("Two"); numberList.add("Three"); combList.add(numberList); ArrayList<ArrayList<String>> combs = combinations(combList); for (ArrayList<String> al: combs) { System.out.println(String.join(" ", al)); } } public static ArrayList<ArrayList<String>> combinations(ArrayList<ArrayList<String>> combList) { if (combList.size() == 0) { ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>(); ret.add(new ArrayList<String>()); return ret; } else { ArrayList<String> levelList = combList.remove(0); ArrayList<ArrayList<String>> subAnswer = combinations(combList); ArrayList<ArrayList<String>> newList = new ArrayList<ArrayList<String>>(); for (ArrayList<String> solList : subAnswer) { for (String s: levelList) { ArrayList<String> newComb = new ArrayList<String>(solList); newComb.add(s); newList.add(newComb); } } return newList; } } }
Improve this answer

Comments

0 
import java.util.Arrays; import java.util.List; public class PrintAllCombinations { public void printCombination(List<List<String>> a, int n, String b) { if (n == a.size()) { System.out.println(b); return; } for (int j = 0; j < a.get(n).size(); j++) printCombination(a, n + 1, b + a.get(n).get(j)); } public static void main(String[] args) { PrintAllCombinations printAllCombinations = new PrintAllCombinations(); List<List<String>> a = Arrays.asList(Arrays.asList("10 ", "20 ", "30 "), Arrays.asList("40 ", "50 ", "60 "), Arrays.asList("70 ", "80 ", "90 ")); printAllCombinations.printCombination(a, 0, ""); } }

outPut:

  • 10 40 70
  • 10 40 80
  • 10 40 90
  • 10 50 70
  • 10 50 80
  • 10 50 90
  • 10 60 70
  • 10 60 80
  • 10 60 90
  • 20 40 70
  • 20 40 80
  • 20 40 90
  • 20 50 70
  • 20 50 80
  • 20 50 90
  • 20 60 70
  • 20 60 80
  • 20 60 90
  • 30 40 70
  • 30 40 80
  • 30 40 90
  • 30 50 70
  • 30 50 80
  • 30 50 90
  • 30 60 70
  • 30 60 80
  • 30 60 90
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.