java - 递归函数获取列表动态数量的组合

Question

我正在尝试编写一个递归函数来从动态列表中获取所有可能的组合。例如，如果我有 3 个列表

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

即使在输出中每个元素都出现一次，我还是希望将输出保持在结构中

List<List<List<elements>>>

我的预期输出是

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

这里列表的数量可以动态变化。所以我需要动态数量的嵌套循环来查找组合。

这是我在尝试什么。请忽略我糟糕的代码。

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

请帮我看看我哪里做错了？

编辑:

我的想法是将所有组合放在一起，这样

{A}

将是答案中最深的列表

{L1,L2,L3}

将是第二级列表。

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

将是外部列表。所以列表的数量在这里并不重要。所有这些都将包含在上述结构中。我在上述结构中的最终输出如下所示

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

Answer 1

您需要一个非常常见的递归模式，您可以在其中维护一个变量，其中包含构建到当前级别的状态。这是给你的一些代码。

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("}");
    }
  }
}

顺便说一句，你可以在没有第 3 级列表的情况下稍微简化它，就像 @dasblinkenlight 建议的那样