Muszę wygenerować wszystkiepartycje danej liczby całkowitej.
Znalazłem ten algorytm Jerome'a ​​Kellehera, dla którego stwierdzono, że jest najbardziej wydajny:

<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>

odniesienie:http://homepages.ed.ac.uk/jkellehe/partitions.php

Nawiasem mówiąc, nie jest całkiem wydajny. Dla danych wejściowych40 zamrozi prawie cały mój system na kilka sekund, zanim wyda swoje wyjście.

Gdyby był to algorytm rekurencyjny, starałbym się ozdobić go funkcją buforowania lub czymś, co poprawiłoby jego wydajność, ale będąc w ten sposób, nie wiem, co robić.

Czy masz jakieś sugestie dotyczące przyspieszenia tego algorytmu? A może możesz zaproponować mi inny, lub inne podejście, aby zrobić kolejne od zera?