java递归创建列表与所有可能的组合

Question

这是问题：我有一些列表。首先，我只是选择字符串列表，让我们2分简单的：[A,B,C]和[W,X,Y,Z] 我需要填写我的permutationResult是ArrayList中的ArrayList这样的：

permutationResult = [[A, W], [A, X], [A, Y], [A, Z], [B, W], [B, X], [B, Y], [B, Z], [C, W], [C, X], [C, Y], [C, Z]] 

我设法得到的组合通过递归，但是当我尝试将结果存储在我的permutationResult列表中时，此列表似乎已被完全擦除，并被每次最后一次置换所取代。我复制下面的代码和代码运行的结果。我添加了一些System.out.println为了注意它出错的地方，但我不知道该怎么做，所以我们欢迎任何帮助。 预先感谢您。 （此代码的执行也低于）

public void permute(ArrayList<ArrayList<String>> all_Lists, ArrayList<ArrayList<String>> permutationResult, ArrayList<String> objectPutInList, int indexOfList) { 
     if ((indexOfList == all_Lists.size()) && (objectPutInList.size() == all_Lists.size())) { 
      permutationResult.add(objectPutInList); 
      System.out.println("-----------> : "+objectPutInList); 
      System.out.println("put in index : "+permutationResult.lastIndexOf(objectPutInList)); 
      System.out.println("combinations are : "+permutationResult); 
      objectPutInList.remove(objectPutInList.size() - 1); 
      System.out.println("2 combinations are : "+permutationResult); 
      System.out.println(""); 
      return; 
     } 
     for (int i = 0; i < all_Lists.get(indexOfList).size(); ++i) 
     { 
      objectPutInList.add(all_Lists.get(indexOfList).get(i)); 
      permute(all_Lists, permutationResult, objectPutInList, indexOfList + 1); 
     } 
     if (objectPutInList.size() != 0){ 
      objectPutInList.remove(objectPutInList.size() - 1); 
     } 
     return; 
    } 

下面是执行：

-----------> : [A, W] 
put in index : 0 
combinations are : [[A, W]] 
2 combinations are : [[A]] 

-----------> : [A, X] 
put in index : 1 
combinations are : [[A, X], [A, X]] 
2 combinations are : [[A], [A]] 

-----------> : [A, Y] 
put in index : 2 
combinations are : [[A, Y], [A, Y], [A, Y]] 
2 combinations are : [[A], [A], [A]] 

-----------> : [A, Z] 
put in index : 3 
combinations are : [[A, Z], [A, Z], [A, Z], [A, Z]] 
2 combinations are : [[A], [A], [A], [A]] 

-----------> : [B, W] 
put in index : 4 
combinations are : [[B, W], [B, W], [B, W], [B, W], [B, W]] 
2 combinations are : [[B], [B], [B], [B], [B]] 

-----------> : [B, X] 
put in index : 5 
combinations are : [[B, X], [B, X], [B, X], [B, X], [B, X], [B, X]] 
2 combinations are : [[B], [B], [B], [B], [B], [B]] 

-----------> : [B, Y] 
put in index : 6 
combinations are : [[B, Y], [B, Y], [B, Y], [B, Y], [B, Y], [B, Y], [B, Y]] 
2 combinations are : [[B], [B], [B], [B], [B], [B], [B]] 

-----------> : [B, Z] 
put in index : 7 
combinations are : [[B, Z], [B, Z], [B, Z], [B, Z], [B, Z], [B, Z], [B, Z], [B, Z]] 
2 combinations are : [[B], [B], [B], [B], [B], [B], [B], [B]] 

-----------> : [C, W] 
put in index : 8 
combinations are : [[C, W], [C, W], [C, W], [C, W], [C, W], [C, W], [C, W], [C, W], [C, W]] 
2 combinations are : [[C], [C], [C], [C], [C], [C], [C], [C], [C]] 

-----------> : [C, X] 
put in index : 9 
combinations are : [[C, X], [C, X], [C, X], [C, X], [C, X], [C, X], [C, X], [C, X], [C, X], [C, X]] 
2 combinations are : [[C], [C], [C], [C], [C], [C], [C], [C], [C], [C]] 

-----------> : [C, Y] 
put in index : 10 
combinations are : [[C, Y], [C, Y], [C, Y], [C, Y], [C, Y], [C, Y], [C, Y], [C, Y], [C, Y], [C, Y], [C, Y]] 
2 combinations are : [[C], [C], [C], [C], [C], [C], [C], [C], [C], [C], [C]] 

-----------> : [C, Z] 
put in index : 11 
combinations are : [[C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z], [C, Z]] 
2 combinations are : [[C], [C], [C], [C], [C], [C], [C], [C], [C], [C], [C], [C]] 

Answer 1

如何以下递归解决方案？ 你可以使用Set为了删除重复。 这里的想法模仿两个for循环。您遍历第一个列表

go(a.subList(1, a.size()), b, acc); 

，然后通过第二

go(a, b.subList(1, b.size()), acc); 

请记住，Java的很少视为首选语言递归问题。

public class Perm { 

    public List<List<String>> perm(List<String> a, List<String> b) { 
     Set<List<String>> acc = new HashSet<>(); 
     go(a, b, acc); 
     return new LinkedList<>(acc); 
    } 

    private void go(List<String> a, List<String> b, Set<List<String>> acc) { 
     if (a.size() == 0 || b.size() == 0) { 
      return; 
     } 
     List<String> aa = new LinkedList<>(); 
     aa.add(a.get(0)); 
     aa.add(b.get(0)); 
     acc.add(aa); 

     go(a.subList(1, a.size()), b, acc); 
     go(a, b.subList(1, b.size()), acc); 
    } 

    public static void main(String[] args) { 
     List<String> a = new LinkedList<>(); 
     a.add("X"); 
     a.add("Y"); 
     a.add("Z"); 

     List<String> b = new LinkedList<>(); 
     b.add("A"); 
     b.add("B"); 
     b.add("C"); 
     b.add("D"); 
     System.out.println(new Perm().perm(a, b)); 
    } 
} 

Answer 2

嗯，我想我想通了！ 这里是我的问题的答案，以防万一我们有一个或几个名单： 谢谢slawekpl您昨天的及时答复。 PS：这是我第一次张贴问题，在这个平台上，所以我道歉，如果我不知道如何正确地显示我的代码:)

public class TestObject { 

    static ArrayList<ArrayList<Object>> permute(Object val, ArrayList<ArrayList<Object>> all_Lists) { 

     ArrayList<ArrayList<Object>> permuteOneList; 
     ArrayList<ArrayList<Object>> permuteSeveralLists = new ArrayList<ArrayList<Object>>(); 

     if (all_Lists.size() != 1) { 
      for (int i = 0; i < all_Lists.get(0).size(); i++) { 
       permuteOneList = permute(all_Lists.get(0).get(i), new ArrayList(all_Lists.subList(1, all_Lists.size()))); 
       if (!val.equals("")) { 
        ArrayList<Object> comb; 
        for (int j = 0; j < permuteOneList.size(); j++) { 
         comb = permuteOneList.get(j); 
         comb.add(0, val); 
         permuteSeveralLists.add(comb); 
        } 
       } else { 
        permuteSeveralLists.addAll(permuteOneList); 
       } 
      } 
      return permuteSeveralLists; 
     } 
     else { 
      permuteOneList = new ArrayList<ArrayList<Object>>(); 
      for (int i = 0; i < all_Lists.get(0).size(); i++) { 
       ArrayList<Object> comb = new ArrayList<Object>(); 
       if (val ==""){ 
        comb.add(all_Lists.get(0).get(i)); 
        permuteOneList.add(comb); 
       } 
       else { 
        comb.add(val); 
        comb.add(all_Lists.get(0).get(i)); 
        permuteOneList.add(comb); 
       } 
      } 
      return permuteOneList; 
     } 

    } 

    public static void main(String[] args) { 
     ArrayList<Object> l1 = new ArrayList<Object>(); 
     l1.add("a"); 
     l1.add("b"); 
     l1.add("c"); 
     l1.add("d"); 
     ArrayList<Object> l2 = new ArrayList<Object>(); 
     l2.add("w"); 
     l2.add("x"); 
     l2.add("y"); 
     l2.add("z"); 
     ArrayList<ArrayList<Object>> all_Lists = new ArrayList<ArrayList<Object>>(); 

     ArrayList<Object> l3 = new ArrayList<Object>(); 
     l3.add("1"); 
     l3.add("2"); 
     l3.add("3"); 
     all_Lists.add(l1); 
     all_Lists.add(l2); 
     all_Lists.add(l3); 
     ArrayList<ArrayList<Object>> permt = permute("", all_Lists); 
     System.out.println("size : " + permt.size()); 
     System.out.println("permutation is : " + permt); 
    } 

}