Check from how many combinations in a list you can create a triangle

Question

I'm writing a Python program that returns out of how many combinations in a list you can create a triangle.

Example:

--> 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]

I only managed to write a function that checks if you can create a triangle out of 3 given edges:

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

I have tried to make a program that does that, but i failed to . I only managed to write a function that checks if you can create a triangle out of 3 given edges 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 — Luke S., Mar 20 '18 at 15:02
[This answer](https://stackoverflow.com/a/18201716/5858851) shows how to get all combinations of 3 items from your list. — pault, Mar 20 '18 at 15:13
You should add that `check` function in the question. Code is not legible in the comments, especially in python where indentation matters. — Graipher, Mar 20 '18 at 15:20

Graipher · Answer 1 · 2018-03-20T15:26:08.083

0

This is quite easy with the function to check if any three sides can make a triangle, check, given by you in the comments:

from itertools import combinations

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

This uses the fact that itertools.combinations gives all possible combinations, here of length 3 of the input, and the fact that bools are integers with True == 1 and False == 0, so we can just sum them to get the number of True elements.

Your check function could also be more explicit:

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

edited Mar 20 '18 at 15:26

answered Mar 20 '18 at 15:18

Graipher

6,891
27
47

Thank you. By the way, is there a way to do this avoiding itertools? – Luke S. Mar 20 '18 at 15:31
@LukeS. Sure, but why would you want to? – Graipher Mar 20 '18 at 15:32
Could you please show me? Itertools.combinations is really slow (when using bigger lists) and I would like to do that optimally. – Luke S. Mar 20 '18 at 15:33
@LukeS. I'm sorry, I don't want to reinvent the wheel just for your fun. But you could have a look at the documentation of [`itertools.combinations`](https://docs.python.org/3/library/itertools.html#itertools.combinations) I linked in the post. It includes a function to which the actual implementation is roughly equivalent. – Graipher Mar 20 '18 at 15:38
I don't mean 'for fun'. I'm just wondering if there is another way to do that (In the more 'logical' way). But still thank you for the answer. – Luke S. Mar 20 '18 at 15:41
@LukeS. Well, I'm not sure how much more logical it can get than "count the number of length-3 combinations from the input which can form a triangle", which is literally the problem statement. – Graipher Mar 20 '18 at 15:43
@LukeS. You will also not get around trying all possible combinations, which grows with `n!`, regardless of the algorithm. The only way to make it less is to recursively first filter out the largest value if it is larger than the second plus third-largest value. Not sure how much better that is, though. – Graipher Mar 20 '18 at 16:19
This check function as well as the one OP provided is incorrect. – pault Mar 20 '18 at 20:54

pault · Answer 2 · 2018-03-21T14:43:52.627

Firstly, your check function is incorrect. From this post, we see that the conditions required are that the sum of each pair of sides is greater than the other side. As @david explained:

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

a + b > c

a + c > b

b + c > a

You are only checking to see if the sum of the two smaller sides is greater than the largest. Furthermore, your function would fail for cases where the largest side is duplicated. For example, the values 1, 4, 4 form a valid triangle but your function check(1, 4, 4) returns False.

That being said, there is very little you can do to avoid checking all combinations of 3 values.

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)]

You could make a marginal speed improvement by sorting the list. This helps because the code can short-circuit because the first condition will fail (and you don't have to check the other two).

For example, these are the sorted combinations of 3 sides from your example list:

>>> 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)]

In the third example, x = 2, y = 3, and z = 789. The first condition (x+y) > z will fail and you won't have to check the other two. I've included some timing results to show that sorting is slightly faster.

Update

If you wanted to avoid duplicates, you can use a set comprehension:

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

Timing Results

# 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

Check from how many combinations in a list you can create a triangle

2 Answers2