Декартово произведение ArrayLists в Java. Перевернутый. Но почему?

Question

Я попытался сгенерировать декартово произведение неизвестного числа ArrayLists (фиксированного типа) на основе этого ответа . Но я нашел что-то странное. Декартовы произведения всегда даются в обратном порядке. Например, если A и B - два списка, элементы B задаются первыми, а элементы A - вторыми в декартовой паре. В чем может быть возможная причина? Как это исправить? Оригинальный ответчик говорит, что порядок в декартовом произведении не имеет значения. Но я думаю, что упорядочение - это главное при создании декартовых произведений, особенно когда каждый набор представляет координаты плоскости.

Модифицированный код:

private static Set<ArrayList<Double>> cartesianProduct(ArrayList<ArrayList<Double>> sets) {
        if (sets.size() < 2)
            throw new IllegalArgumentException(
                    "Can't have a product of fewer than two sets (got " +
                            sets.size() + ")");

        return _cartesianProduct(0, sets);
    }

    private static Set<ArrayList<Double>> _cartesianProduct(int index, ArrayList<ArrayList<Double>> sets) {
        Set<ArrayList<Double>> ret = new HashSet<>();
        if (index == sets.size()) {
            ret.add(new ArrayList<>());
        } else {
            for (Double obj : sets.get(index)) {
                for (ArrayList<Double> set : _cartesianProduct(index + 1, sets)) {
                    set.add(obj);
                    ret.add(set);
                }
            }
        }
        return ret;
    }

Вывод:

ArrayList<Double> l1 = new ArrayList<>(Arrays.asList(1.0, 2.0));
ArrayList<Double> l2 = new ArrayList<>(Arrays.asList(4.0, 5.0));
ArrayList<ArrayList<Double>> l = new ArrayList<>(Arrays.asList(l1, l2));
Set<ArrayList<Double>> a = cartesianProduct(l);

// a = [[4.0, 1.0], [4.0, 2.0], [5.0, 1.0], [5.0, 2.0]]

Answer 1

Этот метод создает декартово произведение в обратном порядке, потому что оно создает произведение "наизнанку" - когда оно возвращается из рекурсии.

Распечатывает значение, возвращаемое каждым уровнем в рекурсии, и вы будете посмотрим, как это происходит.

Второй уровень рекурсии работает в списке B и возвращает [[4], [5]].

Первый уровень рекурсии занимает [[4], [ 5]] и использует метод list.add для добавления элементов из списка A. Этот метод добавляет элементы в конец списка , поэтому получается результат [[4, 1], [5, 1] , [4, 2], [5, 2]].

Как это исправить?

Быстрое исправление - вставка элементов вперед, а не сзади. Вместо set.add(obj) используйте:

set.add(0, obj);

Другой вариант - изменить порядок итерации , чтобы второй уровень рекурсии использовал список A, а первый уровень - список B. Первоначальный вызов для запуска рекурсии будет сделан с sets.size(), и вместо обратного отсчета он должен быть:

    return _cartesianProduct(sets.size() - 1, sets);
...
            for (ArrayList<Double> set : _cartesianProduct(index - 1, sets)) {

Еще один вариант - изменить рекурсию, чтобы продукт был построен на пути вниз рекурсия - "снаружи" - а не на выходе. Этот подход используется в другом ответе на вопрос, на который вы ссылаетесь: { ссылка }

Answer 2

Это происходит из-за рекурсии. Индекс изначально равен 0, поэтому в строке for (ArrayList<Double> set : _cartesianProduct(index + 1, sets)) { ваш код снова вызывает cartesianProduct с index = 1. Он снова достигает этой линии и вызывает cartesianProduct с индексом = 2. Когда он имеет индекс = 2, он достигает своего базового случая и возвращает набор с пустым ArrayList.

. Затем он возвращается к стековому фрейму, где индекс = 1 (помните, obj равен 4, потому что sets.get(1) - ArrayList, содержащий 4 и 6). Он добавляет все двойные числа в sets.get(index) (здесь это 4.0 и 6.0) к их собственным спискам ArrayLists в ret. Затем он достигает конца foreach l oop и возвращает набор, который теперь имеет 2 ArrayLists, один содержит 4.0, а другой 6.0.

То же самое происходит при index = 0, поэтому первый список (или установить) элементы добавляются после элементов второго списка. Вот почему вы получаете обратные результаты.

Чтобы это исправить, вы можете уменьшать индекс каждый раз, переходя от sets.size () к 0, а не наоборот. Чтобы изменить это, вы также можете просто вызвать Collections.reverse () для каждого набора в результате.

//Fix by decrementing index
private static Set<ArrayList<Double>> cartesianProduct(ArrayList<ArrayList<Double>> sets) {
        if (sets.size() < 2)
            throw new IllegalArgumentException(
                    "Can't have a product of fewer than two sets (got " +
                            sets.size() + ")");
//Be sure to start at the end of 'sets' so you can go down by one
        return cartesianProduct(sets.size() - 1, sets);
    }

private static Set<ArrayList<Double>> cartesianProduct(int index, ArrayList<ArrayList<Double>> sets) {
        Set<ArrayList<Double>> ret = new HashSet<>();
//Counting to 0 instead of to the end of the sets ArrayList
        if (index < 0) {
            ret.add(new ArrayList<>());
        } else {
            for (Double obj : sets.get(index)) {
                for (ArrayList<Double> set : cartesianProduct(index - 1, sets)) {
                    set.add(obj);
                    ret.add(set);
                }
            }
        }
        return ret;
    }

//Alternative answer using Collections.reverse
private static Set<ArrayList<Double>> cartesianProduct(ArrayList<ArrayList<Double>> sets) {
        if (sets.size() < 2)
            throw new IllegalArgumentException(
                    "Can't have a product of fewer than two sets (got " +
                            sets.size() + ")");
//This basically goes through the set of sets and reverses each ArrayList
        return cartesianProduct(0, sets).stream().map(Collections::reverse).collect(Collectors.toSet());
    }