Recursive function to get combinations of dynamic number of List

Question

I am trying to write a recursive function to get all posible combination from dynamic number of List. For example if I have 3 Lists

List 1 : {A,B}
List 2 : {B,C}
List 3 : {D}

Even though in the output each element occurs once I would like to keep the output in the structure of

List<List<List<elements>>>

My expected output will be

L1 : A, L2 : B, L3 : D
L1 : A, L2 : C, L3 : D
L1 : B, L2 : B, L3 : D
L1 : B, L2 : C, L3 : D

Here the number of list can change dynamically . So I need dynamic number of nested loop to find combinations.

Here what am I trying. Just ignore my awful code.

public List<List<List<elements>>> combinations(int depth, List<List<elements>> allLists,List<List<List<elements>>> answerList){

if(depth==allList.size())
 return answerList
 }
else{ 
 for(List<element> e : answerList){
    for(int j=0; j<e.size();j++){
      answerList.get(depth).get(j).add(allList.get(depth).get(j));
combinations (depth+1,allLists,answerList)
}
}
}

Please help me where am I doing wrong?

EDIT:

my idea is to keep all combinations together so that

{A}

will be the deepest list in answer

{L1,L2,L3}

will be the second level of list.

{L1,L2,L3},{L1,L2,L3}

will be the outside list. So the number of Lists doest matter here. all will be covered by the above structure. my final output in the above structure is given below

 {
   {
     {A},
     {B},
     {D}
   },
   {
     {A},
     {C},
     {D}
   },
   {
     {B},
     {B},
     {D}
   },
   {
     {B},
     {C},
     {D}
   }
 }

Can you check if this question: https://stackoverflow.com/questions/17192796/generate-all-combinations-from-multiple-lists — sagarr, Nov 04 '18 at 14:07
Can you explain what the list of list of list is supposed to contain? It's a bit difficult to understand your desired output (if you want it in this particular structure). What are the elements of the lists? — RealSkeptic, Nov 04 '18 at 14:24
@dasblinkenlight I have explained my structure in my question. please check my EDIT. Thank you. — kumaran ragunathan, Nov 04 '18 at 14:28
@RealSkeptic I have explained my stucture in EDIT. also consider the element as String now. — kumaran ragunathan, Nov 04 '18 at 14:29
It still looks like your output has two gratuitous levels of lists, i.e. the same output could be represented with `{{A,B,D}, {A,C,D}, {B,B,D}, {B,C,D}}` without losing any information. Am I missing something? — Sergey Kalinichenko, Nov 04 '18 at 14:59

score 2 · Accepted Answer · answered Nov 05 '18 at 05:21

You need a pretty common recursive pattern, where you maintain a variable containing the state built up to the current level. Here's some code for you.

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Main 
{
  public static void recurse(int depth,
                      List<List<String>> current,
                      List<List<List<String>>> result,
                      List<List<String>> lists)
  {
    if (depth == lists.size()) {
      // Copy the list to the result
      result.add(new ArrayList<List<String>>(current));
      return;
    }
    // Iterate over the current-depth list
    List<String> list = lists.get(depth);
    for (String str: list) {
      List<String> elem = Arrays.asList(str);
      current.add(elem);   // Add the next element to the list
      recurse(depth + 1, current, result, lists);
      current.remove(depth);  // Clean up this element
    }
  }

  public static List<List<List<String>>> combinations(List<List<String>> allLists) 
  {
      // We'll fill it in
      List<List<List<String>>> result = new ArrayList<>();

      // Current, partial row in the final result
      List<List<String>> current = new ArrayList<>();

      recurse(0, current, result, allLists);

      return result;
  }

  public static void main(String[] args) {

    System.out.println("Hello World!");

    List<String> list1 = Arrays.asList("A", "B");
    List<String> list2 = Arrays.asList("B", "C", "E");
    List<String> list3 = Arrays.asList("D", "X");

    List<List<String>> allLists = Arrays.asList(list1, list2, list3);

    List<List<List<String>>> result = combinations(allLists);

    // Print
    for (List<List<String>> list: result) {
      System.out.print("{ ");
      for (List<String> elem: list)
        System.out.print("{" + elem.get(0) + "} ");
      System.out.println("}");
    }
  }
}

Btw, you can simplify it a bit without the 3rd level of lists, like @dasblinkenlight suggested

Recursive function to get combinations of dynamic number of List

1 Answers1