Разрезание массива на согласованные части любого размера с рекурсией

Проблема состоит в том, чтобы, учитывая массив, написать функцию генератора, которая даст все комбинации разрезания массива на согласованные части (массивы элементов, которые являются последовательными в данном массиве) любого размера и которые вместе составляют весь заданный массив. Элементы в любой из комбинаций не обязательно должны быть одного размера. Например, учитывая массив [1,2,3,4], я хочу получить: [[1],[2],[3],[4]][[1,2],[3],[4]][[1],[2,3],[4]][[1],[2],[3,4]][[1,2],[3,4]][[1],[2,3,4]][[1,2,3],[4]][[1,2,3,4]]

def powerset_but_consistent(T):

    if len(T)==0:
        return

    for el in T:
        yield el
        for k in range(len(el)):
            yield ([el[:k],el[k:]])
            #for l in range(k, len(el)):
            #    yield ([el[:k],el[k:l],el[l:]])
            powerset_but_consistent([T[:k],T[k:]])


T = [[1,2,3,4,5]]
subsets = [x for x in powerset_but_consistent(T)]
for i in subsets:
    print(i)

И это печатает только те комбинации, которые состоят из двух массивов. Если я раскомментирую то, что я прокомментировал, то он также напечатает комбинации, состоящие из 3 массивов. Если я добавлю еще один внутренний цикл for, он напечатает эти комбинации, состоящие из 4 массивов и так далее... Как я могу использовать рекурсию вместо бесконечных внутренних циклов for? Пришло ли время использовать что-то вроде: для x в powerset_but_consistent (T [some_slicing] или что-то еще)? Мне сложно понять эту конструкцию. Кто-нибудь может помочь?

Какие идеи вы пробовали конкретно?

ggorlen 03.12.2022 16:01

Смотрите также Как задавать домашние вопросы и отвечать на них?. Мы можем помочь вам с конкретным вопросом о попытке, но не с описанием проблемы/нарядом на работу.

ggorlen 03.12.2022 16:09

Я не понимаю, как вы переходите от своего описания к упомянутому вами результату. Пожалуйста, как новый пользователь, пройдите тур и прочитайте Как спросить.

Ulrich Eckhardt 03.12.2022 17:22
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
3
63
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Один из алгоритмов, обычно используемых для вопросов такого типа (перестановки и комбинации), использует поиск в глубину (DFS). Вот ссылка на более похожую, но более сложную проблему с литкодом на разбиении палиндрома, которая использует поиск с возвратом и поиск в глубину. Мое решение основано на этом сообщении leetcode.

Алгоритм

Если моего объяснения недостаточно, перейдите по приведенной выше ссылке на leetcode, это может иметь смысл.

Общая идея заключается в итерации по списку и получении всех комбинаций из текущего элемента путем ресурсного обхода оставшихся элементов после текущих элементов.

Псевдокод

function recursive (list)
    recurise condition
        yield child
    
    for element in remaining-elements:
        // Get the combinations from all elements start from 'element'
        partitions = recursive (...)

        // join the list of elements already explored with the provided combinations
        for every child from partitions:
            yield combination_before + child

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

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

Редактировать: Плохо, я понял, что у меня было фактическое решение до редактирования, я понятия не имел, что это может немного противоречить отдельным правилам сообщества.

Другие вопросы по теме