Comment le code Python pour le partitionnement d'entiers peut-il être rendu plus élégant et plus efficace ?

Code Python élégant pour le partitionnement d'entiers revisité

Dans la quête de l'élégance du code, les programmeurs recherchent souvent des solutions concises et efficaces à des problèmes complexes. L'un de ces défis est le partitionnement d'entiers, la tâche consistant à trouver toutes les partitions d'un entier donné en entiers positifs plus petits.

Affiner la solution

Alors que les tentatives précédentes ont fourni des solutions valables , il leur manquait le niveau d’élégance souhaité. Une solution plus raffinée par un contributeur anonyme offre à la fois compacité et rapidité :

<code class="python">def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p</code>

Comparaison des performances

L'analyse comparative de cette solution par rapport au code original de Nolen révèle un avantage significatif en termes de vitesse :

In [10]: %timeit -n 10 r0 = nolen(20)
1.37 s ± 28.7 ms per loop

In [11]: %timeit -n 10 r1 = list(partitions(20))
979 µs ± 82.9 µs per loop

Solutions supplémentaires

Pour les cas exigeants en termes de calcul, la fonction accel_asc offre des performances encore plus rapides :

<code class="python">def accel_asc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    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>

Cependant, cela vaut la peine notant que cette solution nécessite plus de mémoire que l'implémentation de partitions plus simples.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!