Генерация всех комбинаций списка n уровней глубоко в Java

Question

Я использую следующий код для создания списка комбинаций размера s:

public static <T extends Comparable<? super T>> List<List<T>> combinations(List<T> items, int size) {
        if (size == 1) {
            List<List<T>> result = new ArrayList<>();
            for (T item : items) {
                result.add(Collections.singletonList(item));
            }
            return result ;
        }
        List<List<T>> result = new ArrayList<>();
        for (int i=0; i <= items.size() - size; i++) {
            T firstItem = items.get(i);
            List<List<T>> additionalItems = combinations(items.subList(i+1, items.size()), size-1) ;
            for (List<T> additional : additionalItems) {
                List<T> combination = new ArrayList<>();
                combination.add(firstItem);
                combination.addAll(additional);
                result.add(combination);
            }
        }
        return result ;
}

Дан список со значениями 1, 2 and 3 с размером 2:

List<Integer> items = new ArrayList<Integer>();
items.add(1);
items.add(2);
items.add(3);

combinations(items, 2)

Это приводит к следующим комбинациям:

[1, 2]
[1, 3]
[2, 3]

Я пытаюсь взять этот вывод и сгенерировать 3-й список, где каждая из трех строк из предыдущего вывода теперь объединяется с каждой другой строкой -только этот порядок чувствителен к времени и имеет глубину 'd' .Я ожидаю результатов, подобных следующему:

1 уровень глубины:

[1, 2]
[1, 3]
[2, 3]

2 уровня глубины:

[1, 2], [1, 3]
[1, 2], [2, 3]
[1, 3], [2, 3]
[1, 3], [1, 2]
[2, 3], [1, 2]
[2, 3], [1, 3]

3 уровня глубины:

[[1, 2], [1, 2], [1, 3]]
[[1, 2], [1, 2], [2, 3]]
[[1, 2], [1, 3], [1, 2]]
[[1, 2], [1, 3], [1, 3]]
[[1, 2], [1, 3], [2, 3]]
[[1, 2], [2, 3], [1, 2]]
[[1, 2], [2, 3], [1, 3]]
[[1, 2], [2, 3], [2, 3]]
[[1, 3], [1, 2], [1, 2]]
[[1, 3], [1, 2], [1, 3]]
[[1, 3], [1, 2], [2, 3]]
[[1, 3], [1, 3], [1, 2]]
[[1, 3], [1, 3], [2, 3]]
[[1, 3], [2, 3], [1, 2]]
[[1, 3], [2, 3], [1, 3]]
[[1, 3], [2, 3], [2, 3]]
[[2, 3], [1, 2], [1, 2]]
[[2, 3], [1, 2], [1, 3]]
[[2, 3], [1, 2], [2, 3]]
[[2, 3], [1, 3], [1, 2]]
[[2, 3], [1, 3], [1, 3]]
[[2, 3], [1, 3], [2, 3]]
[[2, 3], [2, 3], [1, 2]]
[[2, 3], [2, 3], [1, 3]]

4 уровня глубины:

[[1, 2], [1, 2], [1, 2], [1, 3]]
[[1, 2], [1, 2], [1, 2], [2, 3]]
[[1, 2], [1, 2], [1, 3], [1, 2]]
[[1, 2], [1, 2], [1, 3], [1, 3]]
[[1, 2], [1, 2], [1, 3], [2, 3]]
[[1, 2], [1, 2], [2, 3], [1, 2]]
[[1, 2], [1, 2], [2, 3], [1, 3]]
[[1, 2], [1, 2], [2, 3], [2, 3]]
[[1, 2], [1, 3], [1, 2], [1, 2]]
[[1, 2], [1, 3], [1, 2], [1, 3]]
[[1, 2], [1, 3], [1, 2], [2, 3]]
[[1, 2], [1, 3], [1, 3], [1, 2]]
[[1, 2], [1, 3], [1, 3], [1, 3]]
[[1, 2], [1, 3], [1, 3], [2, 3]]
[[1, 2], [1, 3], [2, 3], [1, 2]]
[[1, 2], [1, 3], [2, 3], [1, 3]]
[[1, 2], [1, 3], [2, 3], [2, 3]]
[[1, 2], [2, 3], [1, 2], [1, 2]]
[[1, 2], [2, 3], [1, 2], [1, 3]]
[[1, 2], [2, 3], [1, 2], [2, 3]]
[[1, 2], [2, 3], [1, 3], [1, 2]]
[[1, 2], [2, 3], [1, 3], [1, 3]]
[[1, 2], [2, 3], [1, 3], [2, 3]]
[[1, 2], [2, 3], [2, 3], [1, 2]]
[[1, 2], [2, 3], [2, 3], [1, 3]]
[[1, 2], [2, 3], [2, 3], [2, 3]]
[[1, 3], [1, 2], [1, 2], [1, 2]]
[[1, 3], [1, 2], [1, 2], [1, 3]]
[[1, 3], [1, 2], [1, 2], [2, 3]]
[[1, 3], [1, 2], [1, 3], [1, 2]]
[[1, 3], [1, 2], [1, 3], [1, 3]]
[[1, 3], [1, 2], [1, 3], [2, 3]]
[[1, 3], [1, 2], [2, 3], [1, 2]]
[[1, 3], [1, 2], [2, 3], [1, 3]]
[[1, 3], [1, 2], [2, 3], [2, 3]]
[[1, 3], [1, 3], [1, 2], [1, 2]]
[[1, 3], [1, 3], [1, 2], [1, 3]]
[[1, 3], [1, 3], [1, 2], [2, 3]]
[[1, 3], [1, 3], [1, 3], [1, 2]]
[[1, 3], [1, 3], [1, 3], [2, 3]]
[[1, 3], [1, 3], [2, 3], [1, 2]]
[[1, 3], [1, 3], [2, 3], [1, 3]]
[[1, 3], [1, 3], [2, 3], [2, 3]]
[[1, 3], [2, 3], [1, 2], [1, 2]]
[[1, 3], [2, 3], [1, 2], [1, 3]]
[[1, 3], [2, 3], [1, 2], [2, 3]]
[[1, 3], [2, 3], [1, 3], [1, 2]]
[[1, 3], [2, 3], [1, 3], [1, 3]]
[[1, 3], [2, 3], [1, 3], [2, 3]]
[[1, 3], [2, 3], [2, 3], [1, 2]]
[[1, 3], [2, 3], [2, 3], [1, 3]]
[[1, 3], [2, 3], [2, 3], [2, 3]]
[[2, 3], [1, 2], [1, 2], [1, 2]]
[[2, 3], [1, 2], [1, 2], [1, 3]]
[[2, 3], [1, 2], [1, 2], [2, 3]]
[[2, 3], [1, 2], [1, 3], [1, 2]]
[[2, 3], [1, 2], [1, 3], [1, 3]]
[[2, 3], [1, 2], [1, 3], [2, 3]]
[[2, 3], [1, 2], [2, 3], [1, 2]]
[[2, 3], [1, 2], [2, 3], [1, 3]]
[[2, 3], [1, 2], [2, 3], [2, 3]]
[[2, 3], [1, 3], [1, 2], [1, 2]]
[[2, 3], [1, 3], [1, 2], [1, 3]]
[[2, 3], [1, 3], [1, 2], [2, 3]]
[[2, 3], [1, 3], [1, 3], [1, 2]]
[[2, 3], [1, 3], [1, 3], [1, 3]]
[[2, 3], [1, 3], [1, 3], [2, 3]]
[[2, 3], [1, 3], [2, 3], [1, 2]]
[[2, 3], [1, 3], [2, 3], [1, 3]]
[[2, 3], [1, 3], [2, 3], [2, 3]]
[[2, 3], [2, 3], [1, 2], [1, 2]]
[[2, 3], [2, 3], [1, 2], [1, 3]]
[[2, 3], [2, 3], [1, 2], [2, 3]]
[[2, 3], [2, 3], [1, 3], [1, 2]]
[[2, 3], [2, 3], [1, 3], [1, 3]]
[[2, 3], [2, 3], [1, 3], [2, 3]]
[[2, 3], [2, 3], [2, 3], [1, 2]]
[[2, 3], [2, 3], [2, 3], [1, 3]]

Обратите внимание, как на 2 уровнях глубинакомбинация [1, 2], [1, 2] не генерируется, так как между, до или после этого набора нет набора различных чисел.Однако на глубине 3 уровней мы генерируем комбинацию [1, 2], [1, 3], [1, 2], поскольку комбинация [1, 3] присутствует между двумя парами [1, 2].

Аналогично, на 4-х уровнях глубины мы генерируем последовательность [1, 2], [1, 3], [1, 2], [1, 2], которая не эквивалентна последовательности [1, 2], [1, 3], [1, 2], поскольку после [1, 2], [1, 3], [1, 2] есть дополнительная последовательность [1, 2].Мы не генерируем последовательность [1, 2], [1, 2], [1, 2], [1, 2] на 4 уровнях глубиной, так как эта комбинация по существу эквивалентна [1, 2], потому что нет нового набора чисел между, до или после комбинации [1, 2].

Короче говоря, как мне объединить список списков чисел - вплоть до любого количества уровней в глубину (1-4 просто использовался в качестве примера), но на этот раз результат был чувствительным к порядку (так что [1, 2], [1, 3] не эквивалентно [1, 3], [1, 2])?Результат, скорее всего, будет сохранен в List<List<List<Integer>>>.

. Я искал в StackOverflow и видел несколько потоков по созданию комбинаций (таких как этот и этот), но не указали точную ситуацию, описанную выше.

Спасибо

Answer 1

Я считаю, что я сделал то, что вы ищете.Код разбит на четыре отдельных метода (вы не делали различий, если бы он был только 1):

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    clean(result);
    return result;
}

Это то, что делает большинство алгоритма.Во-первых, как и в предоставленной вами функции, он проверяет, равен ли уровень 1, и в этом случае вы можете просто вернуть список списка, как в данном методе.После этого мы перебираем все уровни, которые у нас есть.Сначала мы проверяем, равен ли текущий уровень 1, и в этом случае он будет делать то же самое, как если бы метод вызывался с уровнем 1. Далее мы создаем новый список с именем newResult.Эта переменная в основном является временным значением result, чтобы предотвратить исключение одновременной модификации.Затем мы перебираем все значения уже в result.Мы создаем несколько новых значений на основе того значения, которое у нас есть, и добавляем их к combined.Затем мы добавляем combined в newResult, и алгоритм в основном закончен.Теперь эти циклы не учитываются, когда все значения одинаковы, например, [1, 2], [1, 2], [1, 2], [1, 2].Поэтому мы вызываем метод clean для удаления этих случаев.

public static <T extends Comparable<? super T>> void clean(List<List<List<T>>> list) {
    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : list) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        list.remove(item);
    }
}

Этот метод выполняет все, что находится внутри данного списка, и запускает метод check для элемента.Этот метод объясняется ниже.Если элемент недействителен, он помечается для удаления и удаляется в следующем цикле.

public static <T extends Comparable<? super T>> boolean check(List<List<T>> list) {
    if(list.size() < 2) return true;

    for(int i = 1; i < list.size(); i++) {
        List<T> previous = list.get(i-1);
        List<T> item = list.get(i);

        if(notEqual(previous, item)){
            return true;
        }
    }

    return false;
}

Этот цикл проверяет, является ли данный список допустимым, сравнивая один список с другим, до тех пор, покаон находит два, которые не совпадают.Когда это происходит, список действителен и возвращает true.Если нет, он никогда не вернется, выйдет из цикла и вернет false.

public static <T extends Comparable<? super T>> boolean notEqual(List<T> a, List<T> b) {
    for(int i = 0; i < Math.min(a.size(), b.size()); i++) {
        T ao = a.get(i);
        T bo = b.get(i);

        if(ao.compareTo(bo) != 0)
            return true;
    }

    return false;
}

Этот метод принимает два списка ввода и проверяет, не равны ли элементы внутри них.Он проходит по обоим спискам, получая элементы с одинаковым индексом, и сравнивает их друг с другом.Если они не равны, он возвращает true, а в противном случае завершает цикл и возвращает false.

Обратите внимание, что это просто подтверждение концепции, а не окончательная версия.Многие аспекты этого, безусловно, могут быть улучшены, но это рабочая версия того, что вы просили.

Ссылка на рабочую версию на jDoodle

Если выЕсли у вас есть какие-либо вопросы по любому аспекту или вы хотите что-то прояснить, не стесняйтесь спрашивать!

Редактировать: Я пересмотрел алгоритм, чтобы включить то, что вы просили.Вот новый код:

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int minLevel, int maxLevel) {
    List<List<List<T>>> result = new ArrayList<>();

    for(int i = minLevel; i < maxLevel+1; i++) {
        result.addAll(level(items, i));
    }

    return result;
}

Это перегруженный метод, который позволит вам указать желаемый диапазон уровней.Учитывая минимальный и максимальный уровень, он вернет новый список, содержащий все уровни в этом диапазоне включительно.Как вы сказали, это относительно тривиально, как простой цикл.

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            if(item.size() < i)
                continue;

            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : result) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        result.remove(item);
    }

    return result;
}

Вот пересмотренный метод.Я удалил метод clean и просто поместил его в метод level, так как он вызывался только один раз.Я не думаю, что это действительно возможно, по крайней мере с текущим кодом, чтобы запустить этот метод clean во время алгоритма, потому что в данный момент он работает так, что он генерирует все возможные комбинации для данного уровня, затемпереходит к следующемуЕсли одинаковые комбинации были удалены, на следующем уровне эти комбинации не будут добавлены.

Вот пример: скажем, у меня есть [1, 2], [1, 3], [2, 3].Если бы я пошел на второй уровень, у меня были бы комбинации, указанные в вашем вопросе.Довольно очевидно, верно?Что ж, если бы я затем перешел на уровень 3, используя только результаты уровня 2, я бы пропустил все комбинации, содержащие [1, 2], [1, 2] [...], поскольку этого нет в данном списке.Это - проблема с алгоритмом, и ее определенно можно улучшить.

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

Новая рабочая версия в jDoodle

Редактировать 2: Включение метода clean в алгоритм на самом деле было намного проще, чем я первоначально думал.Вот новый код с парой комментариев:

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    for(int i = 0; i < level; i++) {
        if(i == 0) { // If level is 0, we can just add the items as singleton lists to the result
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>(); // Temporary items that will be added
        for(List<List<T>> item : result) {
            if(item.size() < i) // Make sure we are manipulating items that are on the previous level
                continue;

            List<List<List<T>>> combined = new ArrayList<>(); // The temporary values for this specific item
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>(); // The current list with the value
                current.addAll(item); // Add the current items from result to the list
                current.add(items.get(j)); // Add the current item from items to the list

                if (i == level-1 && !check(current)) { // If this is the last level, and the current list shouldn't be added, skip adding
                    continue;
                }

                combined.add(current); // Add the current list to the combined values
            }

            newResult.addAll(combined); // Add all of the lists in combined to the new result
        }

        result = newResult; // Make result equal to the new result
    }

    return result;
}

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

Я снова планирую полностью переписать алгоритм в гораздо более интеллектуальном формате, но этот код полностью работает прямо сейчас.

Рабочая версия на jDoodle