3个正整数和为n的数组

Question

我使用itertoolscombinations_with_replacement创建了一个生成器，它返回3个正整数的所有组合，这些正整数的总和为n：

def combinations(n):
    for combo in combinations_with_replacement([i for i in range(1,n+1)],3):
        if sum(combo) == n:
            yield(combo)

例如combinations(7)返回(1, 1, 5) (1, 2, 4) (1, 3, 3) (2, 2, 3) 不幸的是，当n的值较大时，这很快就会变得非常缓慢。有没有一种更有效的替代方法？我尝试过使用for循环，尽管每次我都会得到重复的组合。 提前谢谢！你知道吗

Answer 1

您可以使用递归函数来实现这一点：选择一个合适的数字；然后对剩余的大小和总数进行递归。你知道吗

import math

def partition(total, size=3, lowest=1):
    if size == 1:
        return [[total]]
    else:
        result = []

        # At each choice, pick no less than a "fair" proportion of the remaining total.
        #    This avoids duplicating combinations.
        limit = math.ceil(total / size)

        # Iterate `i` through the range [ limit, total-(size-1) ], inclusive
        for i in range(limit, total-size+2):
            for shorter in partition(total-i, size-1):
                result.append(shorter + [i])
    return result

print(partition( 7, 3))
print(partition(12, 3))

输出：

[[2, 2, 3], [1, 3, 3], [1, 2, 4], [1, 1, 5]]
[[4, 4, 4], [3, 5, 4], [2, 6, 4], [1, 7, 4], [3, 4, 5], [2, 5, 5], [1, 6, 5], [3, 3, 6], [2, 4, 6], [1, 5, 6], [2, 3, 7], [1, 4, 7], [2, 2, 8], [1, 3, 8], [1, 2, 9], [1, 1, 10]]

Answer 2

简言之，不，这是一个非常复杂的算法，很快就会归结为O(n ^ 3)

“算法”本身可能不会比O(n ^ 2)更有效，但您可以很容易地将其更改为O(n ^ 2)。你知道吗

def combinations(n):
   for i in range(n - 2): # go up to n and add 1 + 1, assuming you don't want 0 and 0
       for j in range(n - 2): # the same again.
           if i + j >= n:
               continue
           yield (i, j, n - i - j) # there are probably more than just these, keep that in mind.

希望这至少有点帮助。你知道吗

Answer 3

您不必获得三个数字的所有组合。你可以得到两个数的组合，你就知道第三个数是什么了。你知道吗

>>> n = 100
>>> combs_of_three = [(a,b,c) for (a,b,c) in combinations_with_replacement(range(1, n+1), 3) if a+b+c == n]
>>> combs_of_two = [(a,b,n-a-b) for (a,b) in combinations_with_replacement(range(1, n+1), 2) if n-a-b >= b]
>>> combs_of_three == combs_of_two
True

这要快得多：

>>> %timeit [(a,b,c) for (a,b,c) in combinations_with_replacement(range(1, n+1), 3) if a+b+c == n]
9.97 ms ± 97.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

>>> %timeit [(a,b,n-a-b) for (a,b) in combinations_with_replacement(range(1, n+1), 2) if n-a-b >= b]
359 µs ± 2.06 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)