Декартово произведение большого числа множеств

Question

У меня есть List<List<T>> input, и мне нужно сгенерировать декартово произведение из этого. Я пытался использовать Lists.cartesianProduct(input), но проблема в том, что размер декартового произведения больше, чем Integer.MAX_VALUE, и метод выдает исключение. Все алгоритмы, которые я нашел в Интернете, имеют схожие проблемы (они ограничены максимальным размером List, равным Integer.MAX_VALUE, если вы хотите сохранить полную функциональность списка). Единственное решение, о котором я подумал, - это создать собственную реализацию списка, индексированную с long вместо int, но я не смогу использовать List интерфейс, и это было бы очень хлопотно, так что это действительно было бы последним средством. Есть ли другой способ обойти это? Вывод не должен быть списком, если у меня есть все возможные комбинации.

Answer 1

Довольно просто создать решение, которое перебирает декартово произведение и вызывает созданную пользователем функцию вместо построения их списка. Таким образом, полный продукт никогда не будет в памяти. Если вы предпочитаете сохранить результат в файле, вы также можете сделать это, просто предоставив функцию, которая записывает в файл.

<T> void cartesianProduct(List<List<T>> items, Consumer<List<T>> consumer) {
    recurse(items, consumer, new ArrayList<>());
}

<T> void recurse(List<List<T>> items, Consumer<List<T>> consumer, List<T> prefix) {
    if (items.isEmpty()) {
        consumer.accept(prefix);
    } else {
        List<T> first = items.get(0);
        List<List<T>> rest = items.subList(1, items.size());
        for (T item : first) {
            prefix.add(item);
            recurse(rest, consumer, prefix);
            prefix.remove(prefix.size() - 1);
        }
    }
}

Например, это печатает декартово произведение в System.out:

cartesianProduct(List.of(
    List.of("1", "2"), List.of("A", "B"), List.of("!", "@")
), System.out::println);