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

Question

我试图编写代码来解决标准的整数分区问题(维基百科).我写的代码很乱.我需要一个优雅的解决方案来解决问题,因为我想改进我的编码风格.这不是一个家庭作业问题.

Answer 1

比Nolen的功能更小更快:

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

看起来它快了1370倍n = 20.

无论如何,它仍然远离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上找到其他版本:整数分区生成器(Python Recipe).

我使用Python 3.6.1和IPython 6.0.0.

Answer 2

虽然这个答案很好,我建议skovorodkin的答案如下:

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

我已经将解决​​方案与perfplot(我的一个小项目用于此类目的)进行了比较,并发现Nolen的最高投票答案也是最慢的.

通过提供这两个答案skovorodkin是多快.(注意对数刻度.)

要生成图:

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

Answer 4

我需要解决一个类似的问题，即将整数n划分d为非负部分，并进行排列。为此，有一个简单的递归解决方案（请参阅此处）：

def partition(n, d, depth=0):
    if d == depth:
        return [[]]
    return [
        item + [i]
        for i in range(n+1)
        for item in partition(n-i, d, depth=depth+1)
        ]


# extend with n-sum(entries)
n = 5
d = 3
lst = [[n-sum(p)] + p for p in partition(n, d-1)]

print(lst)

输出：

[
    [5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0],
    [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1],
    [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2],
    [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4],
    [0, 0, 5]
]

Answer 5

比公认的响应要快得多，而且看起来也不错。接受的响应多次执行大量相同的工作，因为它多次计算较低整数的分区。例如，当 n=22 时，差异是12.7 秒和 0.0467 秒。

def partitions_dp(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]

代码基本相同，只是我们保存了较小整数的分区，因此我们不必一次又一次地计算它们。

Answer 6

我有点晚了，但我可以提供一个贡献，在某些意义上可能更优雅：

def partitions(n, m = None):
  """Partition n with a maximum part size of m. Yield non-increasing
  lists in decreasing lexicographic order. The default for m is
  effectively n, so the second argument is not needed to create the
  generator unless you do want to limit part sizes.
  """
  if m is None or m >= n: yield [n]
  for f in range(n-1 if (m is None or m >= n) else m, 0, -1):
    for p in partitions(n-f, f): yield [f] + p

只有3行代码。按字典顺序生成它们。可选地允许拼版最大部件尺寸。

对于具有给定数量的部分的分区，我也有上述变化：

def sized_partitions(n, k, m = None):
  """Partition n into k parts with a max part of m.
  Yield non-increasing lists.  m not needed to create generator.
  """
  if k == 1:
    yield [n]
    return
  for f in range(n-k+1 if (m is None or m > n-k+1) else m, (n-1)//k, -1): 
    for p in sized_partitions(n-f, k-1, f): yield [f] + p

编写完上述内容后，我遇到了一个我在大约 5 年前创建的解决方案，但我已经忘记了。除了最大零件尺寸外，这个还提供了附加功能，您可以施加最大长度（而不是特定长度）。FWIW：

def partitions(sum, max_val=100000, max_len=100000):
    """ generator of partitions of sum with limits on values and length """
    # Yields lists in decreasing lexicographical order. 
    # To get any length, omit 3rd arg.
    # To get all partitions, omit 2nd and 3rd args. 

    if sum <= max_val:       # Can start with a singleton.
        yield [sum]

    # Must have first*max_len >= sum; i.e. first >= sum/max_len.
    for first in range(min(sum-1, max_val), max(0, (sum-1)//max_len), -1):
        for p in partitions(sum-first, first, max_len-1):
            yield [first]+p