Print out all possible combinations of an ArrayList<ArrayList<String>> recursively

Question

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

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. — Andy Thomas
– Andy Thomas, Commented Oct 10, 2018 at 16:01
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. — Alain
– Alain, 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? — Yitzak Hernandez
– Yitzak Hernandez, 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. — Alain
– Alain, Commented Oct 11, 2018 at 2:37

Pshemo · Accepted Answer · 2018-10-11 06:54:25Z

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

Deeksha Chaudhari · Accepted Answer · 2021-11-29 09:20:25Z

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

rahul shetty · Accepted Answer · 2018-10-10 19:31:15Z

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

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

Alain · Accepted Answer · 2018-10-11 03:35:42Z

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;
        }
    }
}

Teja Venkata Sai Rajesh Nomula · Accepted Answer · 2021-08-02 06:58:41Z

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

Collectives™ on Stack Overflow

Print out all possible combinations of an ArrayList<ArrayList<String>> recursively

5 Answers 5

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related