所有可能的组合列表，每个列表中有唯一的元素，没有重复的元素

Question

假设我有一个由n个字符串列表组成的列表：

list1 = ["M","G"]; 

list2 = ["VP","P"];

list3 = ["E"]

lists= [ ["M","VP","E"], ["M","P","E"], ["G","VP","E"], ["G","P","E"] ]

result->包含所有输出列表（所有组合）

current->是当前的组合

public static void combination(ArrayList<ArrayList<String>> lists, ArrayList<ArrayList<String>> result, ArrayList<String> current, int k){
    if(k==lists.size()){
        result.add(current);
        current = new ArrayList<String>();
        System.out.println("(if) || k="+k+" || current"+current);
        return;
    }
    for(int t=0;t<lists.get(k).size();t++){
        current.add(lists.get(k).get(t));
        System.out.println("(for) || k="+k+" || current"+current);
        combination(lists, result, current, k+1);
    }
} 

用上述相同示例调用此函数时的输出：

public static void main(String[] args){
    ArrayList<String> l1 = new ArrayList<String>();l1.add("M");l1.add("G");
    ArrayList<String> l2 = new ArrayList<String>();l2.add("VP");l2.add("P");
    ArrayList<String> l3 = new ArrayList<String>();l3.add("E");
    ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
    ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
    ArrayList<String> current = new ArrayList<String>();

    lists.add(l1);lists.add(l2);lists.add(l3);
    combination(lists, result, current, 0);

    for(int i=0;i<result.size();i++){
        System.out.println(result.get(i));
    }

}

(for) || k=0 || current[M]

(for) || k=1 || current[M, VP]

(for) || k=2 || current[M, VP, E]

(if) || k=3 || current[]

(for) || k=1 || current[M, VP, E, P]

(for) || k=2 || current[M, VP, E, P, E]

(if) || k=3 || current[]

(for) || k=0 || current[M, VP, E, P, E, G]

(for) || k=1 || current[M, VP, E, P, E, G, VP]

(for) || k=2 || current[M, VP, E, P, E, G, VP, E]

(if) || k=3 || current[]

(for) || k=1 || current[M, VP, E, P, E, G, VP, E, P]

(for) || k=2 || current[M, VP, E, P, E, G, VP, E, P, E]

(if) || k=3 || current[]

[M, VP, E, P, E, G, VP, E, P, E]

[M, VP, E, P, E, G, VP, E, P, E]

[M, VP, E, P, E, G, VP, E, P, E]

[M, VP, E, P, E, G, VP, E, P, E]

Answer 1

另一种方法，也许容易得多：

public static List<List<String>> combination(List<List<String>> lists){
    if (lists.size() == 1) {
        return lists;
    } else {
        List<List<String>> subcombs = combination(lists.subList(1, lists.size()));
        List<List<String>> result = new ArrayList<>();
        for (String s : lists.get(0)) {
            for (List<String> subcomb : subcombs) {
                List<String> list = new ArrayList<>();
                list.add(s);
                list.addAll(subcomb);
                result.add(list);
            }
        }
        return result;
    }
}

public static void main(String[] args){
    List<String> l1 = Arrays.asList("M", "G");
    List<String> l2 = Arrays.asList("VP", "P");
    List<String> l3 = Arrays.asList("E");
    System.out.println(combination(Arrays.asList(l1, l2, l3)));
    // Output: [[M, VP, E], [M, P, E], [G, VP, E], [G, P, E]]
}

在每个递归步骤中，只需计算子组合，并在当前列表的每个字符串之前