# Find valid triples for a sorted list of integers

I'm working on a problem in which I have an input array, sorted positive unique integers, and have to try to find all possible triples $(x,y,z)$ which satisfy $x+y>z$ and $x<y<z$. For example, $(1,2,3)$ is not a valid triple since $1+2$ is not $> 3$, and $(3,4,5)$ is a valid triple since $3<4<5$ and $3+4>5$.

This code leverages binary search, and I'm wondering if this can be improved in terms of time complexity. Please also help to point out any code issues/bugs or improvement areas.

Implementation

# find upper bound of value, including value itself
def findUpperBound(numbers, value, start):
if not numbers:
raise 'value eror'
low = start
high = len(numbers) - 1
while low <= high:
mid = (low + high) // 2
if numbers[mid] == value:
return mid
elif numbers[mid] > value:
high = mid - 1
else:
low = mid + 1
# if reach here, means find an upper bound
return low

if __name__ == "__main__":

result = set()
numbers=[1,2,4,5,6,7,8,10]
for i in range(0, len(numbers)-2):
for j in range(i+1, len(numbers)-1):
k = findUpperBound(numbers, numbers[i] + numbers[j], j+1)
for p in range(j+1, k):

print result


Output

set([(5, 7, 10), (4, 6, 8), (5, 7, 8), (4, 8, 10), (6, 8, 10), (2, 6, 7), (5, 6, 7), (4, 5, 6), (5, 6, 8), (2, 4, 5), (5, 6, 10), (2, 7, 8), (5, 8, 10), (4, 7, 8), (7, 8, 10), (6, 7, 8), (2, 5, 6), (6, 7, 10), (4, 5, 7), (4, 5, 8), (4, 6, 7), (4, 7, 10)])

• Is there a reason why 3 and 9 are not in numbers? – Graipher Oct 6 '16 at 10:36
• @Graipher, it is just for testing purpose. If you find any bugs or algorithm performance improvement areas, please let me know. :) – Lin Ma Oct 6 '16 at 21:28

### 1. Review

1. The code is not portable to Python 3 due to the use of the print statement.

2. The code is not fully organized into functions: most of it runs at the top level of the module. This makes it hard to understand and hard to test.

3. It's not allowed in Python to raise a string. If you try this you'll get the following:

>>> findUpperBound([], 0, 0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "cr143389.py", line 4, in findUpperBound
raise 'value eror'
TypeError: exceptions must derive from BaseException


What you need is something like:

raise ValueError("no numbers")

4. But it isn't right to raise an exception when there are no numbers to search. The function is supposed to return an index into numbers that is greater than or equal to start and points after all entries less than or equal to value. So if numbers is empty then it should return start.

5. Functions for binary search of a sorted sequence are already built into Python: see the bisect module. In this case you'll want to use bisect.bisect_left.

6. The two nested loops for i and j can be combined into a single loop using itertools.combinations. This leads to the revised code:

from itertools import combinations, islice
from bisect import bisect_left

def triangles(seq):
"""Given a sorted sequence of unique numbers, generate triples a, b, c
that satisfy the triangle inequality, that is, where a + b > c.

"""
for i, j in combinations(range(len(seq) - 1), 2):
a, b = seq[i], seq[j]
for c in islice(seq, j + 1, bisect_left(seq, a + b, lo=j+1)):
yield a, b, c

7. In the general case, the number of triples satisfying the conditions is $O(n^3)$. Consider as an extreme case the set of numbers $\{n, n+1, \ldots, 2n\}$: in this case every triple satisfies the conditions. So in general you don't lose any asymptotic efficiency by iterating over all the triples:

for triple in combinations(numbers, 3):
a, b, c = triple
if a + b > c:
yield triple


I think time complexity is the same of your algorithm and my algorithm.

Yes, the algorithms are identical. The point of using itertools.combinations is to reduce the length of the code and make it clearer, not to change the behaviour.

Wondering if you are thinking of any better algorithm which could improve the time complexity even better?

See §1.7 above — in the worst case there are $O(n^3)$ triples satisfying the conditions, so no algorithm can have runtime $o(n^3)$ in the general case. Possibly for some distributions of inputs it would be possible to do better, but I don't know.