Если вы заинтересованы в создании (лексически) упорядоченных целочисленных разделов, то есть уникальных неупорядоченных наборов из S натуральных чисел (без 0), которые суммируются с N, попробуйте следующее. (неупорядоченный просто означает, что [1,2,1] и [1,1,2] являются одним и тем же разделом)
Проблема не требует рекурсии и быстро решается, потому что концепция поиска следующего лексического ограниченного раздела на самом деле очень проста ...
В концепции: начиная с последнего добавления (целое число), найдите первый экземпляр, где разница между двумя добавлениями больше 1. Разбейте раздел на две в этой точке. Удалите 1 из более высокого целого числа (которое будет последним целым числом в одной части) и добавьте 1 к более низкому целому числу (первое целое число последней части). Затем найдите первый лексически упорядоченный раздел для последней части, имеющей новое наибольшее целое число в качестве максимального значения добавления. Я использую Sage, чтобы найти первый лексический раздел, потому что он быстро освещается, но это легко сделать без него. Наконец, объедините две части и вуаля! У вас есть следующий лексический раздел N с частями S.
например. [6,5,3,2,2] -> [6,5], [3,2,2] -> [6,4], [4,2,2] -> [6,4], [ 4,3,1] -> [6,4,4,3,1]
Итак, в Python и вызове Sage для незначительной задачи поиска первого лексического раздела по n и s частям ...
from sage.all import *
def most_even_partition(n,s): # The main function will need to recognize the most even partition possible (i.e. last lexical partition) so it can loop back to the first lexical partition if need be
most_even = [int(floor(float(n)/float(s)))]*s
_remainder = int(n%s)
j = 0
while _remainder > 0:
most_even[j] += 1
_remainder -= 1
j += 1
return most_even
def portion(alist, indices):
return [alist[i:j] for i, j in zip([0]+indices, indices+[None])]
def next_restricted_part(p,n,s):
if p == most_even_partition(n,s):return Partitions(n,length=s).first()
for i in enumerate(reversed(p)):
if i[1] - p[-1] > 1:
if i[0] == (s-1):
return Partitions(n,length=s,max_part=(i[1]-1)).first()
else:
parts = portion(p,[s-i[0]-1]) # split p (soup?)
h1 = parts[0]
h2 = parts[1]
next = list(Partitions(sum(h2),length=len(h2),max_part=(h2[0]-1)).first())
return h1+next
Если вам нужны нули (а не фактические целочисленные разбиения), то функции нуждаются только в небольших модификациях.