4
\$\begingroup\$

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)])
\$\endgroup\$
  • 1
    \$\begingroup\$ Is there a reason why 3 and 9 are not in numbers? \$\endgroup\$ – Graipher Oct 6 '16 at 10:36
  • \$\begingroup\$ @Graipher, it is just for testing purpose. If you find any bugs or algorithm performance improvement areas, please let me know. :) \$\endgroup\$ – Lin Ma Oct 6 '16 at 21:28
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks Gareth, (1) your method of using combination tries to find any combinations of i and j, then tries to use binary search to find bound value, (2) my method sequentially iterate j (inner loop) based on the value of i (outer loop), I think my method is faster since for example, if we have two elements 3 and 4, my method just enumerate (3,4) then trying to find bound, but you enumerate twice for both (3,4) and (4,3) and trying to find bound. It seems your method double times of binary search? \$\endgroup\$ – Lin Ma Oct 7 '16 at 4:58
  • 1
    \$\begingroup\$ @LinMa: Did you try it? \$\endgroup\$ – Gareth Rees Oct 7 '16 at 9:22
  • 1
    \$\begingroup\$ @LinMa: see updated answer. \$\endgroup\$ – Gareth Rees Oct 9 '16 at 20:20
  • 1
    \$\begingroup\$ @LinMa: see updated answer. \$\endgroup\$ – Gareth Rees Oct 10 '16 at 8:55
  • 1
    \$\begingroup\$ @LinMa: (i) You need to be more explicit about what you mean here — it's not clear to me what "distributed in a uniform way" means when applied to sets of numbers. (ii) I think this is getting outside the scope of a code review and you might be better off asking a new question, for example on cs.stackexchange.com. \$\endgroup\$ – Gareth Rees Oct 10 '16 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.