Comment les générateurs Python peuvent-ils résoudre le problème de partitionnement d'entiers avec élégance ?

Solution Python élégante pour le partitionnement d'entiers

Le partitionnement d'entiers fait référence à la division d'un entier positif en une somme d'entiers positifs uniques. Une solution élégante en Python utilise une fonction génératrice pour générer efficacement toutes les partitions possibles d'un entier n donné.

La solution fournie, issue d'ActiveState de Python, utilise la récursion :

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

Ce générateur génère toutes les partitions par ordre décroissant de leur plus grande partie, ce qui rend le processus plus rapide pour les partitions plus petites. Son temps d'exécution surpasse les autres approches, comme le démontrent les tests de comparaison temporelle.

La solution nécessite plus de mémoire par rapport à un algorithme plus optimisé comme accel_asc. Néanmoins, sa simplicité et sa lisibilité en font un outil précieux pour résoudre les problèmes de partitionnement d'entiers.

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!