检查列表中有多少个组合可以创建三角形

Question

我正在编写一个Python程序，它返回一个列表中可以创建三角形的多少个组合。你知道吗

示例：

--> test([1,1,3])
0 #you cant make a triangle out of 1,1,3 (the only combination in this list)

--> test([2,789,5,3,3237,4])
3 #you can make a triangle out of [2,5,4],[5,3,4] and [2,4,3]

我只写了一个函数，检查你是否能用3条给定的边创建一个三角形：

def check(a,b,c):
    n = max((a,b,c))
    x = 0
    y = 0
    for i in [a,b,c]:
        if i != n:
            if x == 0:
                x = i
            elif y == 0:
                y = i 
    return (x+y)>n

Answer 1

使用函数可以很容易地检查任意三条边是否可以构成三角形，check，由您在注释中给出：

from itertools import combinations

def test(x):
    return sum(check(*comb) for comb in combinations(x, 3))

这使用了^{}给出所有可能的组合的事实，这里是输入的长度3，bool是带有True == 1和False == 0的整数，所以我们可以对它们求和以得到True元素的数量。你知道吗

您的check函数也可以更加明确：

def check(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

Answer 2

首先，你的检查功能不正确。从this post，我们看到所需的条件是每对边的和大于另一侧。作为@davidexplained：

Let's say that a, b, c is the sides of the triangle. Therefore, it must be satisfy this criteria:

1. a + b > c
2. a + c > b
3. b + c > a

你只需要检查两个较小的边的和是否大于最大的边。此外，在最大的一方被复制的情况下，您的函数将失败。例如，值1, 4, 4形成有效的三角形，但函数check(1, 4, 4)返回False。你知道吗

也就是说，您几乎无法避免检查3个值的所有组合。你知道吗

from itertools import combinations
[(x, y, z) for (x, y, z) in combinations(test, 3) 
 if ((x+y) > z) and ((x+z) > y) and ((y+z) > x)]
#[(2, 5, 4), (2, 3, 4), (5, 3, 4)]

通过对列表进行排序，可以略微提高速度。这很有帮助，因为代码可能会短路，因为第一个条件将失败（而且您不必检查其他两个条件）。你知道吗

例如，以下是示例列表中3个边的排序组合：

>>> test = [2,789,5,3,3237,4]
>>> list(combinations(sorted(test), 3))
[(2, 3, 4),
 (2, 3, 5),
 (2, 3, 789),
 (2, 3, 3237),
 (2, 4, 5),
 (2, 4, 789),
 (2, 4, 3237),
 (2, 5, 789),
 (2, 5, 3237),
 (2, 789, 3237),
 (3, 4, 5),
 (3, 4, 789),
 (3, 4, 3237),
 (3, 5, 789),
 (3, 5, 3237),
 (3, 789, 3237),
 (4, 5, 789),
 (4, 5, 3237),
 (4, 789, 3237),
 (5, 789, 3237)]

在第三个示例中，x = 2、y = 3和z = 789。第一个条件(x+y) > z将失败，您不必检查其他两个条件。我已经包括了一些计时结果，以表明排序是稍微更快。你知道吗

更新

如果要避免重复，可以使用集合理解：

{(x, y, z) for (x, y, z) in combinations(sorted(test), 3) if 
 ((x+y) > z) and ((x+z) > y) and ((y+z) > x)}

计时结果

# make list of random numbers
import numpy as np
N = 100
test = [np.random.randint(0,5000) for i in range(N)]

# without sorting
%%timeit
[(x, y, z) for (x, y, z) in combinations(test, 3) 
 if ((x+y) > z) and ((x+z) > y) and ((y+z) > x)]
#10 loops, best of 3: 76.1 ms per loop

# with sorting
%%timeit
[(x, y, z) for (x, y, z) in combinations(sorted(test), 3) if 
 ((x+y) > z) and ((x+z) > y) and ((y+z) > x)]
#10 loops, best of 3: 65.1 ms per loop