找出所有满足 i+j+k=n 的三元组 i,j,k

Question

我已经对此进行了编码，但这很长：

for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if i + j + k == n:

有没有聪明的方法让它运行得更快？目前是 O(n^3) 这很可悲。

Answer 1

最里面的循环似乎是多余的，因为一旦你有了 i 和 j，k 就免费了：

for i in range(n + 1):
    for j in range(n + 1):
        if i+j <= n:
            print((i, j, n-i-j))

如果我们想要添加到 n 的唯一数字的三元组，那么也许这可行：

for i in range(n + 1):
    for j in range(i, (n - i)//2 + 1):
        out.append((i, j, n-i-j))

Answer 2

有几种方法可以使代码运行更快。

使用列表理解。语法 [ReturnThing ForLoops 条件]

从上一个循环到达的地方开始每个循环。这样可以避免重复

def MakeTriplet(n):                                                                          
    return [(i,j,k) for i in range(0,n+1) for j in range(i,n+1) for k in range(j,n+1) if (i+j+k)==n]

Answer 3

有一些可能的解决方案 - 您实际上不需要在所有这些解决方案中循环直到 N，最后一个数字完全免费。

记住三元组中的所有数字都必须是正数（否则答案是无限的）。

如果不包括排列（即 (1,2,3) 与 (3,2,1) 是同一个三元组），从小到大：

def iter_triplets(n):
    # This is the smallest number, can't be more than 1/3 of n
    for i in range(0, n//3 + 1):
        sum_left = n-i
        # This is the second smallest, can't be more than 1/2 of the sum_left or less than the first by definition
        for j in range(i, sum_left//2 + 1):
            yield (i, j, sum_left-j)  # Last number is calculated.


>>> list(iter_triplets(6))  
[(0, 0, 6), (0, 1, 5), (0, 2, 4), (0, 3, 3), (1, 1, 4), (1, 2, 3), (2, 2, 2)]
>>> list(iter_triplets(10))
[(0, 0, 10), (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6), (0, 5, 5), (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 2, 6), (2, 3, 5), (2, 4, 4), (3, 3, 4)]

如果不包括排列（即 (1,2,3) 与 (3,2,1) 是同一个三元组），从大到小：

import math
def iter_triplets(n):
    # This is the biggest number, can't be less than 1/3 of n
    for i in range(n, math.ceil(n/3) - 1, -1):
        sum_left = n-i
        # This is the second biggest number, can't be less than 1/2 of the sum_left and more than first number by definition.
        # ceil to correct rounding errors.
        for j in range(min(sum_left, i), math.ceil((sum_left)/2) - 1, -1):
            yield (i, j, sum_left-j)  # Last number is calculated.


>>> list(iter_triplets(10))
[(10, 0, 0), (9, 1, 0), (8, 2, 0), (8, 1, 1), (7, 3, 0), (7, 2, 1), (6, 4, 0), (6, 3, 1), (6, 2, 2), (5, 5, 0), (5, 4, 1), (5, 3, 2), (4, 4, 2), (4, 3, 3)]

如果包含排列（即 (1,2,3) 是 与 [=14= 不同的 三元组]), 从小到大：

def iter_triplet_permutations(n):
    for i in range(0, n+1):
        sum_left = n-i
        for j in range(0, sum_left+1):
            yield (i, j, sum_left-j)

>>> list(iter_triplet_permutations(5)) 
[(0, 0, 5), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 4, 1), (0, 5, 0), (1, 0, 4), (1, 1, 3), (1, 2, 2), (1, 3, 1), (1, 4, 0), (2, 0, 3), (2, 1, 2), (2, 2, 1), (2, 3, 0), (3, 0, 2), (3, 1, 1), (3, 2, 0), (4, 0, 1), (4, 1, 0), (5, 0, 0)]

找出所有满足 i+j+k=n 的三元组 i,j,k

Find all triplets i,j,k such that i+j+k=n

python

math

discrete-mathematics