Wie können Python-Generatoren das Ganzzahlpartitionierungsproblem elegant lösen?

Elegante Python-Lösung zur Ganzzahlpartitionierung

Partitionierung von Ganzzahlen bezieht sich auf die Division einer positiven Ganzzahl in eine Summe eindeutiger positiver Ganzzahlen. Eine elegante Lösung in Python nutzt eine Generatorfunktion, um alle möglichen Partitionen einer gegebenen ganzen Zahl n effizient zu erzeugen.

Die bereitgestellte Lösung aus Pythons ActiveState verwendet Rekursion:

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

Dieser Generator generiert Alle Partitionen werden in absteigender Reihenfolge ihres größten Teils sortiert, wodurch es bei kleineren Partitionen schneller geht. Seine Laufzeit übertrifft andere Ansätze, wie in Zeitvergleichstests gezeigt wurde.

Die Lösung erfordert mehr Speicher im Vergleich zu einem optimierteren Algorithmus wie accel_asc. Dennoch ist es aufgrund seiner Einfachheit und Lesbarkeit ein wertvolles Werkzeug zur Lösung ganzzahliger Partitionierungsprobleme.

Das obige ist der detaillierte Inhalt vonWie können Python-Generatoren das Ganzzahlpartitionierungsproblem elegant lösen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!