Is there a way to find all the permutations of a collection of colelctions BUT some elements would exclude eachother

Question

I'm trying to find permutations in a collection of collections with a condition, that elements from each inner collection may only appear once.

So for example I have a List of Lists: [[a,b],[c,d],[e,f]] and my result would be something like:

[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...

Or at least help me with some links to answers -- I am a begginer and still do not know the correct phrases needed to ask questions using the search engine.

Possible duplicate of [Cartesian product of arbitrary sets in Java](https://stackoverflow.com/questions/714108/cartesian-product-of-arbitrary-sets-in-java) — azro, Apr 04 '19 at 19:15
Would `[b]` and `[a,d]` also be valid? What about the empty list? — Sean Van Gorder, Apr 04 '19 at 19:37
yes, [b], [a,d] satisfy the requirements since they would each take a maximum of 1 elements from each set. They would be valid. Empty list would be valid as well, since it would take 0 elements from each Set (maximum of 1 from each). — theory, Apr 04 '19 at 20:39

Sean Van Gorder · Accepted Answer · 2019-04-04T20:50:43.843

Recursive solution with unsorted output:

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;
}

For the example lists [[a,b],[c,d],[e,f]] the output is:

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

If you need them sorted by size, this one is about 2-3x slower:

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;
}

Output:

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

Is there a way to find all the permutations of a collection of colelctions BUT some elements would exclude eachother

1 Answers1