Проблема состоит в том, чтобы, учитывая массив, написать функцию генератора, которая даст все комбинации разрезания массива на согласованные части (массивы элементов, которые являются последовательными в данном массиве) любого размера и которые вместе составляют весь заданный массив. Элементы в любой из комбинаций не обязательно должны быть одного размера.
Например, учитывая массив [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] или что-то еще)? Мне сложно понять эту конструкцию. Кто-нибудь может помочь?
Смотрите также Как задавать домашние вопросы и отвечать на них?. Мы можем помочь вам с конкретным вопросом о попытке, но не с описанием проблемы/нарядом на работу.
Я не понимаю, как вы переходите от своего описания к упомянутому вами результату. Пожалуйста, как новый пользователь, пройдите тур и прочитайте Как спросить.
Один из алгоритмов, обычно используемых для вопросов такого типа (перестановки и комбинации), использует поиск в глубину (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
Основной концепцией этого является использование поиска в глубину и, возможно, выяснение рекурсивного условия, поскольку это действительно заняло у меня некоторое время.
Вы также можете оптимизировать код, сохраняя результаты глубоких рекурсивных операций в словаре и получая к ним доступ при повторном посещении в следующих итерациях. Я также уверен, что где-то есть оптимальное решение для динамического программирования. Удачи, надеюсь помог
Редактировать: Плохо, я понял, что у меня было фактическое решение до редактирования, я понятия не имел, что это может немного противоречить отдельным правилам сообщества.
Какие идеи вы пробовали конкретно?