Это определенно имеет NP-хард-чувство. В частности, вопрос о том, возможно ли сделать 2 разбиения против 1, является вопросом о том, является ли надлежащее подмножество всех элементов, кроме последнего, суммированием с отрицательным последним, что является вариантом проблемы суммы подмножеств. Так что даже проверка того, что ответ не может быть улучшен в дальнейшем путем разбиения одного из разделов, вероятно, является NP-полной!
Но как можно решить эту проблему на практике?
Шаг 1 - произвестиструктура данных, представляющая все возможные разделы, включая первый элемент, сумма которого равна 0. Это может быть решено как в стандартном алгоритме суммы подмножеств. С идеей двусвязного списка, из которого мы можем получить информацию. (Двусвязный список, как правило, будет пропорционален размеру вашего массива, умноженному на количество найденных различных сумм, но при декодировании он может привести к экспоненциальному количеству разделов.
Вдвойне связанные списки могут заставить вашу голову вращаться, поэтому вы, вероятно, захотите использовать синтаксический сахар следующим образом:
from collections import namedtuple
Node = namedtuple('Node', ['ind', 'prev'])
Paths = namedtuple('Paths', ['node', 'prev'])
Где ind - это индекс в вашем массиве, node - это всегда Node, а prev - это всегда Paths или None.
И теперь Node говорит "включить этот индекс и любой допустимый путь в следующие предыдущие варианты". А Paths говорит "здесь есть узел, который ведет сюда,и предыдущие пути для других способов. "
С этим мы можем сделать следующее:
# We only want paths that take the 0th index.
ways_to_get_to_n = {elements[0], Paths(Node(0, None), None)}
for i in range(1, len(elements)):
element = elements[i]
new_ways_to_get_n = {}
for value, ways in ways_to_get_n.items():
new_ways_to_get_n[value] = ways
for value, ways in ways_to_get_n.items():
if value + element not in new_ways_to_get_n:
new_ways_to_get_n[value + element] = Paths(Node(i, ways), None)
else:
new_ways_to_get_n[value + element] = Paths(Node(i, ways), new_ways_to_get_n[value + element])
ways_to_get_n = new_ways_to_get_n
Когда вы закончите, ways_to_get_n[0] - это довольно краткая структура данных, которую можно использоватьс двойной рекурсией, чтобы пройти через все разделы, которые включают в себя первый элемент. Однако есть проблема. Эти разделы могут иметь 0 разделов внутри. Так что, когда вы идете по двойной рекурсии, носите остроумиеh это структура данных всех значений, которые вы можете достичь (тот же самый старый трюк с суммой подмножества), и заканчиваться рано, когда появляется 0. (Эта бухгалтерия может показаться дополнительной работой, но на самом деле она сэкономит вам гораздо больше.)
И теперь вы можете рекурсивно находить минимальные разделы с первым элементом. Затем рекурсивно ищите, как разбить оставшиеся элементы. Каждый раз, когда вы это делаете, вы сравниваете с лучшим, что у вас есть на данный момент, и если это улучшение, запишите это.
Когда вы прошли через все пути его разложения, все готово.
Предполагая массивы целых чисел (так что псевдополиномиальная сумма подмножества, вероятно, будет работать в вашу пользу), это позволит вам довольно эффективно выполнять рекурсию на минимальных разделах. Что является лучшим рекурсивным взрывом, чем наивный подход. Но это будет на много больше, чем вы думаете.
Я подозреваю, что сортировка массива по возрастанию абсолютного значения в качестве первого шага сделает этот алгоритм более эффективным, сделав фильтр "неприводимым"раздел "может выйти из рекурсии рано, когда у вас еще много элементов.