50

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

4

11 回答 11

71

比 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 食谱）。

我使用 Python 3.6.1 和 IPython 6.0.0。

于 2017-05-26T20:05:55.233 回答
46

虽然这个答案很好，但我建议 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)

于 2012-04-05T22:16:12.383 回答
19

我已经将该解决方案与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",
)
于 2017-07-26T17:15:05.477 回答
10

我需要解决一个类似的问题，即用排列将整数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]
]
于 2017-07-27T11:10:25.267 回答
5

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

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]

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

于 2016-06-20T18:16:38.283 回答
5

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

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
于 2017-12-16T18:54:18.340 回答
3

这是一个递归函数，它使用一个堆栈，我们在其中按升序存储分区的数量。它足够快且非常直观。

# get the partitions of an integer

Stack = []
def Partitions(remainder, start_number = 1):
    if remainder == 0:
        print(" + ".join(Stack))
    else:
        for nb_to_add in range(start_number, remainder+1):
            Stack.append(str(nb_to_add))
            Partitions(remainder - nb_to_add, nb_to_add)
            Stack.pop()

当堆栈已满时（堆栈元素的总和对应于我们想要的分区数），我们打印它，删除它的最后一个值并测试要存储在堆栈中的下一个可能值。当所有下一个值都经过测试后，我们再次弹出堆栈的最后一个值并返回最后一个调用函数。这是一个输出示例（带有 8 个）：

Partitions(8)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1 + 3
1 + 1 + 1 + 1 + 2 + 2
1 + 1 + 1 + 1 + 4
1 + 1 + 1 + 2 + 3
1 + 1 + 1 + 5
1 + 1 + 2 + 2 + 2
1 + 1 + 2 + 4
1 + 1 + 3 + 3
1 + 1 + 6
1 + 2 + 2 + 3
1 + 2 + 5
1 + 3 + 4
1 + 7
2 + 2 + 2 + 2
2 + 2 + 4
2 + 3 + 3
2 + 6
3 + 5
4 + 4
8

递归函数的结构很容易理解，如下图所示（对于整数 31）：

remainder对应于我们想要分区的剩余数字的值（上例中的 31 和 21）。 start_number对应分区的第一个数字，其默认值为1（上例中为1和5）。

如果我们想在列表中返回结果并获取分区数，我们可以这样做：

def Partitions2_main(nb):
    global counter, PartitionList, Stack
    counter, PartitionList, Stack = 0, [], []
    Partitions2(nb)
    return PartitionList, counter

def Partitions2(remainder, start_number = 1):
    global counter, PartitionList, Stack
    if remainder == 0:
        PartitionList.append(list(Stack))
        counter += 1
    else:
        for nb_to_add in range(start_number, remainder+1):
            Stack.append(nb_to_add)
            Partitions2(remainder - nb_to_add, nb_to_add)
            Stack.pop()

最后，上面显示的函数的一大优点Partitions是它可以很容易地找到一个自然数的所有组合（两个组合可以有相同的一组数字，但在这种情况下顺序不同）：我们只需要删除变量并在循环start_number中将其设置为 1 。for

# get the compositions of an integer

Stack = []
def Compositions(remainder):
    if remainder == 0:
        print(" + ".join(Stack))
    else:
        for nb_to_add in range(1, remainder+1):
            Stack.append(str(nb_to_add))
            Compositions(remainder - nb_to_add)
            Stack.pop()

输出示例：

Compositions(4)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3
2 + 1 + 1
2 + 2
3 + 1
4
于 2019-06-06T12:37:31.040 回答
2

我认为这里的食谱可能是优雅的。它简洁（20 行长）、快速且基于 Kelleher 和 O'Sullivan 的作品，其中引用了该作品：

def aP(n):
    """Generate partitions of n as ordered lists in ascending
    lexicographical order.

    This highly efficient routine is based on the delightful
    work of Kelleher and O'Sullivan.

    Examples
    ========

    >>> for i in aP(6): i
    ...
    [1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 2]
    [1, 1, 1, 3]
    [1, 1, 2, 2]
    [1, 1, 4]
    [1, 2, 3]
    [1, 5]
    [2, 2, 2]
    [2, 4]
    [3, 3]
    [6]

    >>> for i in aP(0): i
    ...
    []

    References
    ==========

    .. [1] Generating Integer Partitions, [online],
        Available: http://jeromekelleher.net/generating-integer-partitions.html
    .. [2] Jerome Kelleher and Barry O'Sullivan, "Generating All
        Partitions: A Comparison Of Two Encodings", [online],
        Available: http://arxiv.org/pdf/0909.2331v2.pdf

    """
    # The list `a`'s leading elements contain the partition in which
    # y is the biggest element and x is either the same as y or the
    # 2nd largest element; v and w are adjacent element indices
    # to which x and y are being assigned, respectively.
    a = [1]*n
    y = -1
    v = n
    while v > 0:
        v -= 1
        x = a[v] + 1
        while y >= 2 * x:
            a[v] = x
            y -= x
            v += 1
        w = v + 1
        while x <= y:
            a[v] = x
            a[w] = y
            yield a[:w + 1]
            x += 1
            y -= 1
        a[v] = x + y
        y = a[v] - 1
        yield a[:w]
于 2016-04-28T17:47:11.527 回答
1 
# -*- coding: utf-8 -*-
import timeit

ncache = 0
cache = {}


def partition(number):
    global cache, ncache
    answer = {(number,), }
    if number in cache:
        ncache += 1
        return cache[number]
    if number == 1:
        cache[number] = answer
        return answer
    for x in range(1, number):
        for y in partition(number - x):
            answer.add(tuple(sorted((x, ) + y)))
    cache[number] = answer
    return answer


print('To 5:')
for r in sorted(partition(5))[::-1]:
    print('\t' + ' + '.join(str(i) for i in r))

print(
    'Time: {}\nCache used:{}'.format(
        timeit.timeit(
            "print('To 30: {} possibilities'.format(len(partition(30))))",
            setup="from __main__ import partition",
            number=1
        ), ncache
    )
)

或https://gist.github.com/sxslex/dd15b13b28c40e695f1e227a200d1646

于 2017-05-25T17:26:33.857 回答
0

我不知道我的代码是否最优雅，但出于研究目的，我不得不多次解决这个问题。如果你修改 

sub_nums

变量，您可以限制分区中使用的数字。

def make_partitions(number):
    out = []
    tmp = []
    sub_nums = range(1,number+1)
    for num in sub_nums:
        if num<=number:
            tmp.append([num])
        for elm in tmp:
            sum_elm = sum(elm)
            if sum_elm == number:
                out.append(elm)
            else:
                for num in sub_nums:
                    if sum_elm + num <= number:
                         L = [i for i in elm]
                         L.append(num)
                         tmp.append(L)
    return out
于 2012-04-05T20:55:29.837 回答
-1 
F(x,n) = \union_(i>=n) { {i}U g| g in F(x-i,i) }

只需实现此递归。F(x,n) 是总和为 x 且其元素大于或等于 n 的所有集合的集合。

于 2012-04-05T21:03:19.267 回答