Есть ли способ найти все перестановки коллекции коллекций, но некоторые элементы исключают друг друга?

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