获取数字的所有整数分区

Question

我基本上有这个问题Get all numbers that add up to a number但我还需要0才能被包括在内。

接受的答案我试过了，从0开始，基本上是这样的

def sum_to_n(n, size, limit=None):
    """Produce all lists of `size` positive integers in decreasing order
    that add up to `n`."""

    if size == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = 0
    stop = min(limit, n - size + 1) + 1
    for i in range(start, stop):
        for tail in sum_to_n(n - i, size - 1, i):
            yield [i] + tail

对于较小的数字效果很好，但是当我将较大的数字作为目标时，它开始表现得很奇怪。例如：

for partition in sum_to_n(10,7):
    print(partition)

输出就像

0   0   0   0   0   0   10
1   0   0   0   0   0   9
1   1   0   0   0   0   8
1   1   1   0   0   0   7
1   1   1   1   0   0   6
1   1   1   1   1   0   5
1   1   1   1   1   1   4
2   0   0   0   0   0   8
2   1   0   0   0   0   7
2   1   1   0   0   0   6
2   1   1   1   0   0   5
2   1   1   1   1   0   4
2   1   1   1   1   1   3
2   2   0   0   0   0   6
2   2   1   0   0   0   5
2   2   1   1   0   0   4
2   2   1   1   1   0   3
2   2   1   1   1   1   2
2   2   2   0   0   0   4
2   2   2   1   0   0   3
2   2   2   1   1   0   2
2   2   2   1   1   1   1
3   0   0   0   0   0   7
3   1   0   0   0   0   6
3   1   1   0   0   0   5
3   1   1   1   0   0   4
3   1   1   1   1   0   3
3   1   1   1   1   1   2
3   2   0   0   0   0   5
3   2   1   0   0   0   4
3   2   1   1   0   0   3
3   2   1   1   1   0   2
3   2   1   1   1   1   1
4   0   0   0   0   0   6
4   1   0   0   0   0   5
4   1   1   0   0   0   4
4   1   1   1   0   0   3
4   1   1   1   1   0   2
4   1   1   1   1   1   1

这里显然不包括 5 5 0 0 0 0 0 的情况。它还有像 1 1 1 1 1 1 4 和 4 1 1 1 1 1 1 这样的重复情况，我不想要.这段代码有什么问题？我该如何修改它或关于如何解决问题的任何其他想法？谢谢！

Answer 1

我想这就是你想要的：

def sum_to_n2(n, size, limit=None):
    if limit is None:
        limit = n
    if size == 1:
        if n <= limit:
            yield[n]
    else:
        for i in range(0, limit+1):
            for tail in sum_to_n2(n - i, size - 1, min(i, n-i)):
                yield[i] + tail


print(list(sum_to_n2(10, 7)))

与您的代码的不同之处：

在开始时检查 limit is None，该函数有一个更简单的 if .. else（主要是装饰性的，我觉得更容易理解并且不需要 return 离开那里);
如果 size == 1，你总是让步 [n]，但只有在 n <= limit;
您将范围限制计算为 min(limit, n - size + 1) + 1，但这很难在精神上追踪（更是如此，因为范围就在它附近停止）；我只是说限制是 i（我们要添加到序列中的数字，因此不再允许更大的数字）和 n-i（余数，我们不需要更大的数字）中的最小值比那个了），然后将其传递给 min(i, n-i).

我还没有对您的代码中计算错误的位置进行完整逻辑分析，但如果我将 n <= limit 条件添加到您的代码中，它就不再包含零。我相信您在将值与我的算法实现进行比较时可以弄清楚，但我认为我的算法更简洁一些，所以更可取。

6, 3 的输出已经表明您的代码存在问题，该代码比 10, 7 短。 sum_to_n(5, 3) 的输出：

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

例如，请注意 [2, 1, 2] 和 [2, 2, 1] 中的重复项。

我对 sum_to_n2(5, 3) 的输出：

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

就个人而言，但这纯粹是风格，我更喜欢这个修改后的实现的输出：

def sum_to_n2(n, size, limit=None):
    if limit is None:
        limit = n
    if size == 1:
        if n <= limit:
            yield[n]
    else:
        for i in range(limit, -1, -1):
            for tail in sum_to_n2(n - i, size - 1, min(i, n - i)):
                yield[i] + tail

这导致（sum_to_n2(5, 3)）：

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

它通过反转 for 循环中的范围来做到这一点。

顺便说一句，这是一个非递归的单行代码，但它慢得像泥:):

def sum_to_n_one_liner (n, sized):
    set(tuple(sorted(t)) for t in filter(lambda s: sum(s) == n, product(*[range(n)]*size)))

它通过天真地做需要做的事情来工作：

取数字从0到n，size次
计算笛卡尔积，得到这些数字的所有可能组合
只保留总和为 n
对生成的元组进行排序，只保留唯一的元组

Answer 2

为了得到不重复的分区，您可以定义函数，使其只生成非降序的结果。

def partition(N,size):
    if size == 1 :
        yield (N,)                           # base case, only 1 part
        return
    for a in range(N//size+1):               # smaller part followed by
        for p in partition(N-a*size,size-1): # equal or larger ones
            yield (a, *(n+a for n in p))     # recursing on delta only

输出：

for p in partition(10,7): print(p)
(0, 0, 0, 0, 0, 0, 10)
(0, 0, 0, 0, 0, 1, 9)
(0, 0, 0, 0, 0, 2, 8)
(0, 0, 0, 0, 0, 3, 7)
(0, 0, 0, 0, 0, 4, 6)
(0, 0, 0, 0, 0, 5, 5)
(0, 0, 0, 0, 1, 1, 8)
(0, 0, 0, 0, 1, 2, 7)
(0, 0, 0, 0, 1, 3, 6)
(0, 0, 0, 0, 1, 4, 5)
(0, 0, 0, 0, 2, 2, 6)
(0, 0, 0, 0, 2, 3, 5)
(0, 0, 0, 0, 2, 4, 4)
(0, 0, 0, 0, 3, 3, 4)
(0, 0, 0, 1, 1, 1, 7)
(0, 0, 0, 1, 1, 2, 6)
(0, 0, 0, 1, 1, 3, 5)
(0, 0, 0, 1, 1, 4, 4)
(0, 0, 0, 1, 2, 2, 5)
(0, 0, 0, 1, 2, 3, 4)
(0, 0, 0, 1, 3, 3, 3)
(0, 0, 0, 2, 2, 2, 4)
(0, 0, 0, 2, 2, 3, 3)
(0, 0, 1, 1, 1, 1, 6)
(0, 0, 1, 1, 1, 2, 5)
(0, 0, 1, 1, 1, 3, 4)
(0, 0, 1, 1, 2, 2, 4)
(0, 0, 1, 1, 2, 3, 3)
(0, 0, 1, 2, 2, 2, 3)
(0, 0, 2, 2, 2, 2, 2)
(0, 1, 1, 1, 1, 1, 5)
(0, 1, 1, 1, 1, 2, 4)
(0, 1, 1, 1, 1, 3, 3)
(0, 1, 1, 1, 2, 2, 3)
(0, 1, 1, 2, 2, 2, 2)
(1, 1, 1, 1, 1, 1, 4)
(1, 1, 1, 1, 1, 2, 3)
(1, 1, 1, 1, 2, 2, 2)

获取数字的所有整数分区

get all integer partition of a number

python

math