有没有办法找到一组共情的所有排列，但有些元素会相互排除

Question

我试图在集合集合中找到排列，条件是每个内部集合中的元素只能出现一次。例如，我有一个列表列表：[[a，b]，[c，d]，[e，f]]，我的结果将是这样的：[a][c][e]...[a,c] ('a' appeared and excluded 'b')[b,d][c,e]...[a, c, e][b, d, f][a, c, f]and so on...或者至少帮我一些答案的链接 - 我是一个乞丐，仍然不知道使用搜索引擎提问所需的正确短语。

Answer 1

具有未排序输出的递归解决方案：

public static <T> List<List<T>> permutations(List<List<T>> lists) {

    return permutations(lists, new ArrayList<>());

}

private static <T> List<List<T>> permutations(List<List<T>> lists, List<T> prefix) {

    if (lists.isEmpty()) return Arrays.asList(prefix);

    List<T> head = lists.get(0);

    List<List<T>> tail = lists.subList(1, lists.size());

    List<List<T>> result = new ArrayList<>();

    for (T t : head) {

        List<T> p = new ArrayList<>(prefix);

        p.add(t);

        result.addAll(permutations(tail, p));

    }

    result.addAll(permutations(tail, prefix));

    return result;

}

对于示例列表，输出为：[[a,b],[c,d],[e,f]]

[[a, c, e], [a, c, f], [a, c], [a, d, e], [a, d, f], [a, d], [a, e], [a, f], [a],

 [b, c, e], [b, c, f], [b, c], [b, d, e], [b, d, f], [b, d], [b, e], [b, f], [b],

 [c, e], [c, f], [c], [d, e], [d, f], [d], [e], [f], []]

如果您需要按大小排序，则此速度大约慢2-3倍：

public static <T> List<List<T>> permutations(List<List<T>> lists) {

    List<List<T>> result = new ArrayList<>();

    for (int i = 0; i <= lists.size(); i++) {

        result.addAll(permutations(lists, i));

    }

    return result;

}

private static <T> List<List<T>> permutations(List<List<T>> lists, int count) {

    if (count == 0) return Arrays.asList(new ArrayList<>());

    List<List<T>> result = new ArrayList<>();

    for (int i = 0; i < lists.size() - count + 1; i++) {

        for (T t : lists.get(i)) {

            for (List<T> r : permutations(lists.subList(i + 1, lists.size()), count - 1)) {

                r = new ArrayList<>(r);

                r.add(0, t);

                result.add(r);

            }

        }

    }

    return result;

}

输出：

[[], [a], [b], [c], [d], [e], [f], [a, c], [a, d], [a, e], [a, f],

 [b, c], [b, d], [b, e], [b, f], [c, e], [c, f], [d, e], [d, f],

 [a, c, e], [a, c, f], [a, d, e], [a, d, f], [b, c, e], [b, c, f], [b, d, e], [b, d, f]]