为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

郎朗坤 2022-09-22 16:08:49

我试图在集合集合中找到排列,条件是每个内部集合中的元素只能出现一次。


例如,我有一个列表列表:[[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...

或者至少帮我一些答案的链接 - 我是一个乞丐,仍然不知道使用搜索引擎提问所需的正确短语。


查看完整描述

1 回答

?
HUX布斯

TA贡献1537条经验 获得超6个赞

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


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]]



查看完整回答
反对 回复 2022-09-22

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信