python: generando particiones enteras
Necesito generar todo elparticiones de un entero dado.
Encontré este algoritmo de Jerome Kelleher para el cual se dice que es el más eficiente:
<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>
referencia:http://homepages.ed.ac.uk/jkellehe/partitions.php
Por cierto, no es del todo eficiente. Para una entrada como40
congela casi todo mi sistema durante unos segundos antes de dar su salida.
Si se tratara de un algoritmo recursivo, trataría de decorarlo con una función de almacenamiento en caché o algo para mejorar su eficiencia, pero al ser así, no puedo averiguar qué hacer.
¿Tiene algunas sugerencias sobre cómo acelerar este algoritmo? ¿O me puede sugerir otro o un enfoque diferente para hacer otro desde cero?