Elegant Python code for Integer Partitioning [closed]

by

A smaller and faster than Nolen’s function:

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

Let’s compare them:

In [10]: %timeit -n 10 r0 = nolen(20)
1.37 s ± 28.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [11]: %timeit -n 10 r1 = list(partitions(20))
979 µs ± 82.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [13]: sorted(map(sorted, r0)) == sorted(map(sorted, r1))
Out[14]: True

Looks like it’s 1370 times faster for n = 20.

Anyway, it’s still far from accel_asc:

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]

It’s not only slower, but requires much more memory (but apparently is much easier to remember):

In [18]: %timeit -n 5 r2 = list(accel_asc(50))
114 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 5 loops each)

In [19]: %timeit -n 5 r3 = list(partitions(50))
527 ms ± 8.86 ms per loop (mean ± std. dev. of 7 runs, 5 loops each)

In [24]: sorted(map(sorted, r2)) == sorted(map(sorted, r3))
Out[24]: True

You can find other versions on ActiveState: Generator For Integer Partitions (Python Recipe).

I use Python 3.6.1 and IPython 6.0.0.

More Related Contents:

  1. What happens when start value < end value with range() cmd in Python?
  2. Check if all elements in a list are identical
  3. Permutations between two lists of unequal length
  4. Pythonic way to check if a list is sorted or not
  5. About Python’s built in sort() method
  6. Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraint
  7. Weighted random selection with and without replacement
  8. What is the fastest way to flatten arbitrarily nested lists in Python? [duplicate]
  9. Efficient way to apply multiple filters to pandas DataFrame or Series
  10. Rolling or sliding window iterator?
  11. What is the best way to get all the divisors of a number?
  12. How to efficiently compare two unordered lists (not sets)?
  13. Python – Is a dictionary slow to find frequency of each character?
  14. How to implement a binary tree?
  15. In Python, what is the fastest algorithm for removing duplicates from a list so that all elements are unique *while preserving order*? [duplicate]
  16. Best way to determine if a sequence is in another sequence?
  17. Mapping a range of values to another
  18. How to check whether two lists are circularly identical in Python
  19. Find elements of array one nearest to elements of array two
  20. Complexity of list.index(x) in Python
  21. Fast prime factorization module
  22. Why does Python’s itertools.permutations contain duplicates? (When the original list has duplicates)
  23. Python: find closest string (from a list) to another string
  24. In Python, how do you find the index of the first value greater than a threshold in a sorted list?
  25. String similarity metrics in Python [duplicate]
  26. What is the time complexity of heapq.nlargest?
  27. creating a spiral array in python?
  28. Understanding change-making algorithm
  29. What is this odd sorting algorithm?
  30. counting combinations and permutations efficiently

Leave a Comment