4 个字符串列表的所有可能组合

Question

所以我有 4 个字符串列表：

List<String> a={"abc","def"};
List<String> b={"abc","def"};
List<String> c={"abc","def"};
List<String> d={"abc","def"};

从这 4 个列表中生成所有可能的字符串组合的最佳方法是什么？

到目前为止，我已经使用非常基本的代码实现了这一点：

for(String i:a) {
    for(String j:b) {
        for(String k:c) {
            for(String l:d) {
                //do work
            }
        }
    }
}

Answer 1

您可以使用递归方法。

在每一步，您只处理一个列表，“猜测”要添加到目前的解决方案中的元素，然后递归解决“较小”的问题，减少一个列表：

public static <T> void getCombination(List<T>... lists) {
    if (lists == null) return;
    getCombinations(new ArrayList<T>(), 0, lists);
}
private static <T> void getCombinations(List<T> soFar, int i, List<T> ... lists) {
    if (i == lists.length) { //no more lists left:
        //do work on soFar, for example:
        System.out.println(soFar);
    }
    else { 
        for (T t : lists[i]) {
            soFar.add(t); //"guess" item
            getCombinations(soFar, i+1, lists); //recurse on rest of lists
            soFar.remove(soFar.size()-1); //cleanup
        }
    }
}

调用上面的：

public static void main(String args[]) {
    List<String> a= Arrays.asList("abc","def");
    List<String> b= Arrays.asList("abc","def");
    List<String> c=Arrays.asList("abc","def");
    List<String> d=Arrays.asList("abc","def");
    getCombination(a,b,c,d);
}

你会得到：

[abc, abc, abc, abc]
[abc, abc, abc, def]
[abc, abc, def, abc]
[abc, abc, def, def]
[abc, def, abc, abc]
[abc, def, abc, def]
[abc, def, def, abc]
[abc, def, def, def]
[def, abc, abc, abc]
[def, abc, abc, def]
[def, abc, def, abc]
[def, abc, def, def]
[def, def, abc, abc]
[def, def, abc, def]
[def, def, def, abc]
[def, def, def, def]

这种方法可以处理任意数量的此类列表，并且列表可以具有任意大小，但请注意，解决方案的大小（和运行时间）是列表数量的指数，但这是可以预期的，因为任何解决方案将尝试通过所有组合的路径将必须经历指数数量的此类。