Cartesian product of an arbitrary number of sets

Знаете ли вы несколько удобных библиотек Java, которые позволяют создавать декартово произведение двух (или более) наборов?

Например: у меня есть три набора. Один с объектами класса Person, второй с объектами класса Gift и третий с объектами класса GiftExtension .

Я хочу сгенерировать один набор, содержащий все возможные тройки Person-Gift-GiftExtension .

Количество наборов может варьироваться, поэтому я не могу сделать это во вложенном цикле foreach. При некоторых условиях моему приложению необходимо создать произведение пары Person-Gift, иногда это тройное Person-Gift-GiftExtension, иногда могут быть даже наборы Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension и т.д.

Редактировать: Удалены предыдущие решения для двух наборов. Подробности смотрите в истории редактирования.

Вот способ сделать это рекурсивно для произвольного числа наборов:

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    if (sets.length < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                sets.length + ")");

    return _cartesianProduct(0, sets);
}

private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

Обратите внимание, что невозможно сохранить какую-либо информацию об универсальном типе вместе с возвращаемыми наборами. Если бы вы заранее знали, из скольких наборов вы хотели получить произведение, вы могли бы определить универсальный кортеж для хранения такого количества элементов (например, Triple<A, B, C>), но в Java нет способа иметь произвольное количество универсальных параметров.

Это довольно старый вопрос, но почему бы не использовать CartesianProduct от Guava?

Приведенный ниже метод создает декартово произведение списка list строк:

protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> resultLists = new ArrayList<List<T>>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<T>());
        return resultLists;
    } else {
        List<T> firstList = lists.get(0);
        List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
        for (T condition : firstList) {
            for (List<T> remainingList : remainingLists) {
                ArrayList<T> resultList = new ArrayList<T>();
                resultList.add(condition);
                resultList.addAll(remainingList);
                resultLists.add(resultList);
            }
        }
    }
    return resultLists;
}

Пример:

System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));

приведет к этому:

[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]

Количество наборов может варьироваться, поэтому я не могу сделать это во вложенном цикле foreach.

Две подсказки:

• A x B x C = A x (B x C)


• Рекурсия