Find valid triples for a sorted list of integers

Question

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):
                result.add((numbers[i], numbers[j], numbers[p]))

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

Answer 1

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
   

2. Answers to questions

1. In comments, you wrote:

   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.

2. You asked:

   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.

3. You asked:

   What do you think is the time complexity of current algorithm you are writing in general (I mean average)?

   Before you can describe the average runtime of an algorithm, you have to specify the distribution of inputs. With knowing the distribution of inputs, it's impossible to say.