How Can Python Code for Integer Partitioning Be Made More Elegant and Efficient?

Elegant Python Code for Integer Partitioning Revisited

In the pursuit of code elegance, programmers often seek concise and efficient solutions to complex problems. One such challenge is Integer Partitioning, the task of finding all partitions of a given integer into smaller positive integers.

Refining the Solution

While previous attempts have provided valid solutions, they lacked the desired level of elegance. A more refined solution by an anonymous contributor offers both compactness and speed:

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

Performance Comparison

Benchmarking this solution against Nolen's original code reveals a significant speed advantage:

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

Additional Solutions

For computationally demanding cases, the accel_asc function provides even faster performance:

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

However, it is worth noting that this solution requires more memory than the simpler partitions implementation.

The above is the detailed content of How Can Python Code for Integer Partitioning Be Made More Elegant and Efficient?. For more information, please follow other related articles on the PHP Chinese website!