用于整数分区的优雅Python代码

Question

我尝试编写代码来解决标准的整数分区问题(Wikipedia)。我写的代码一团糟。我需要一个优雅的解决方案来解决这个问题，因为我想改进我的编码风格。这不是一个家庭作业问题。

Answer 1

虽然这个答案很好，但我还是推荐的答案如下：

>>> def partition(number):
...     answer = set()
...     answer.add((number, ))
...     for x in range(1, number):
...         for y in partition(number - x):
...             answer.add(tuple(sorted((x, ) + y)))
...     return answer
... 
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])

如果您想要所有排列(即(1，3)和(3，1))，请将answer.add(tuple(sorted((x, ) + y))更改为answer.add((x, ) + y)

Answer 2

一个比诺伦函数更小更快的函数：

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

让我们对它们进行比较：

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

看起来比n = 20快1370倍。

不管怎么说，离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]

它不仅速度慢，而且需要更多的内存(但显然更容易记住)：

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

你可以在ActiveState上找到其他版本：Generator For Integer Partitions (Python Recipe)。

我使用Python3.6.1和IPython 6.0.0。

Answer 3

我将该解决方案与perfplot (我的一个小项目，用于此目的)进行了比较，发现诺伦的投票最多的答案也是最慢的。

skovorodkin提供的两个答案都要快得多。(请注意log-scale。)

​

​

要生成绘图，请执行以下操作：

import perfplot
import collections


def nolen(number):
    answer = set()
    answer.add((number,))
    for x in range(1, number):
        for y in nolen(number - x):
            answer.add(tuple(sorted((x,) + y)))
    return answer


def skovorodkin(n):
    return set(skovorodkin_yield(n))


def skovorodkin_yield(n, I=1):
    yield (n,)
    for i in range(I, n // 2 + 1):
        for p in skovorodkin_yield(n - i, i):
            yield (i,) + p


def accel_asc(n):
    return set(accel_asc_yield(n))


def accel_asc_yield(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 tuple(a[: k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[: k + 1])


def mct(n):
    partitions_of = []
    partitions_of.append([()])
    partitions_of.append([(1,)])
    for num in range(2, n + 1):
        ptitions = set()
        for i in range(num):
            for partition in partitions_of[i]:
                ptitions.add(tuple(sorted((num - i,) + partition)))
        partitions_of.append(list(ptitions))
    return partitions_of[n]


perfplot.show(
    setup=lambda n: n,
    kernels=[nolen, mct, skovorodkin, accel_asc],
    n_range=range(1, 17),
    logy=True,
    # https://stackoverflow.com/a/7829388/353337
    equality_check=lambda a, b: collections.Counter(set(a))
    == collections.Counter(set(b)),
    xlabel="n",
)