如何使Python代码更高效？

Question

我是新手。 我有一个代码，它显示所有可能达到某个数字的和。 但它的复杂性太高，而且当数字太高时，它需要花费太长的时间。我怎样才能把它重构成更简单的东西呢？你知道吗

import itertools

def combos(n):

    result = []
    for i in range(n,0,-1):
        for seq in itertools.combinations_with_replacement(range(1,n+1), i):
            if sum(seq) == n:
                seq = list(seq)
                result.append(seq)
    return(result)

combos(4)

输出：

[[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]

Answer 1

递归版本可以如下所示：

def combinations_max_sum(sum_max, i_max=None):

    if sum_max == 0:
        return [()]

    if not i_max or i_max > sum_max:
        i_max = sum_max

    combinations = [(i, *right_part)
                    for i in range(i_max, 0, -1)
                    for right_part in combinations_max_sum(sum_max-i, i_max=i)]

    return combinations

测试：

print(combinations_max_sum(4)) # [(4,), (3, 1), (2, 2), (2, 1, 1), (1, 1, 1, 1)]
print(combinations_max_sum(4, i_max=1)) # [(1, 1, 1, 1)]
print(combinations_max_sum(5))
# [(5,), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)]

分解问题的思想是：一组组合可以写成一个数字，它与所有的组合连在一起，其总和是n减去第一个数字。你知道吗

一个不处理重复的简单代码可以是这样的：

def combinations_with_repetition(n):

    if n == 0:
        return [()]

    combinations = [(i, *right_part)  # concatenation
                    for i in range(1, n+1)  # for all possible first number 
                    for right_part in combinations_with_repetition(n-i)]
                    # ^ all possible combinations
                    #   given the first number i

    return combinations

它给出：

combinations_with_repetition(3)
# [(1, 2), (1, 1, 1), (2, 1), (3,)]

(1, 2)和(2, 1)是相似的，为了防止出现这种情况，添加了i_max参数（参见第一个函数）。这里的意思是总是按降序排列。右边的数字总是等于或小于左边的数字。这个最大值作为参数传递，循环从它开始，而不是请求的总和。你知道吗