CODEWITHSUNDEEP
javaloopsfor-looprecursion
kumaran ragunathan
kumaran ragunathan

Reputation: 447

Recursive function to get combinations of dynamic number of List

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

Upvotes: 3

Views: 253

Answers (1)

Marcin Zukowski
Marcin Zukowski

Reputation: 4719

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

Upvotes: 2

Related Questions