python: генерация целочисленных разделов
Мне нужно сгенерировать всеперегородки данного целого числа.
Я нашел этот алгоритм Джерома Келлехера, для которого он считается наиболее эффективным:
<code>def accelAsc(n): a = [0 for i in range(n + 1)] k = 1 a[0] = 0 y = n - 1 while k != 0: x = a[k - 1] + 1 k -= 1 while 2*x <= y: a[k] = x y -= x k += 1 l = k + 1 while x <= y: a[k] = x a[l] = y yield a[:k + 2] x += 1 y -= 1 a[k] = x + y y = x + y - 1 yield a[:k + 1] </code>
reference: http://homepages.ed.ac.uk/jkellehe/partitions.php
Кстати, это не совсем эффективно. Для входа типа40
он замораживает почти всю мою систему на несколько секунд, а затем выдает результат.
Если бы это был рекурсивный алгоритм, я бы попытался украсить его функцией кэширования или чем-то еще, чтобы повысить его эффективность, но я так и не могу понять, что делать.
Есть ли у вас предложения о том, как ускорить этот алгоритм? Или вы можете предложить мне другой, или другой подход, чтобы сделать еще один с нуля?