5 Best Ways to Check for Pythagorean Triplets in Python Lists

Rate this post

πŸ’‘ Problem Formulation: This article provides solutions for identifying the presence of Pythagorean triplets within a given list in Python. A Pythagorean triplet consists of three integers a, b, and c, such that a^2 + b^2 = c^2. Given an input list, for example [3, 1, 4, 6, 5], the desired output would be True as (3, 4, 5) forms a Pythagorean triplet.

Method 1: Brute Force Approach

The brute force approach involves three nested loops that check every possible triplet in the list to determine if any meet the condition for Pythagorean triplets. This method is easy to understand but is not efficient as it has a time complexity of O(n^3), making it slower for large lists.

Here’s an example:

def find_pythagorean_triplets(lst):
    for a in lst:
        for b in lst:
            for c in lst:
                if a**2 + b**2 == c**2:
                    return True
    return False

# Test the function
print(find_pythagorean_triplets([3, 1, 4, 6, 5]))

True

This code defines a function find_pythagorean_triplets() that iterates over all combinations of three elements from the given list. If it finds a combination satisfying the Pythagorean triplet condition, it returns True. Otherwise, it will return False after checking all possible combinations.

Method 2: Sorting and Binary Search

By sorting the list and using binary search, we can find Pythagorean triplets more efficiently than brute force. This method reduces the time complexity to O(n^2 log n). The list is first sorted, and then for each pair (a, b), we use binary search to check for the existence of c.

Here’s an example:

from bisect import bisect_left

def is_triplet(c, lst):
    index = bisect_left(lst, c)
    return index < len(lst) and lst[index] == c

def find_pythagorean_triplets(lst):
    lst.sort()
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            a = lst[i]
            b = lst[j]
            c_squared = a**2 + b**2
            if is_triplet(c_squared**0.5, lst):
                return True
    return False

# Test the function
print(find_pythagorean_triplets([3, 1, 4, 6, 5]))

True

This snippet sorts the input list and iterates over each unique pair (a, b) to calculate c^2. It then uses bisect_left() from the bisect module to perform a binary search for the square root of c^2 in the sorted list. If c is found, it means a triplet exists.

Method 3: Hashing

Hashing allows checking for triplets in O(n^2) time on average by using a set to store squares of all elements. For each pair (a, b), we can check if c^2 exists in the hash set, which significantly reduces lookup time compared to the previous methods.

Here’s an example:

def find_pythagorean_triplets(lst):
    squares = set(x**2 for x in lst)
    for a in lst:
        for b in lst:
            if a**2 + b**2 in squares:
                return True
    return False

# Test the function
print(find_pythagorean_triplets([3, 1, 4, 6, 5]))

True

The code creates a set containing the squares of all the numbers in the list. The function then checks for every pair (a, b) if a^2 + b^2 is present in the set, suggesting that (a, b, c) is a Pythagorean triplet. The use of a set allows constant-time lookups.

Method 4: Using List Comprehension and Any Function

We can combine list comprehension with the any() function to write a more Pythonic and concise function. This approach takes advantage of Python’s expressiveness, although it does not offer any performance improvement over hashing.

Here’s an example:

def find_pythagorean_triplets(lst):
    squares = set(x**2 for x in lst)
    return any(a**2 + b**2 in squares for a in lst for b in lst)

# Test the function
print(find_pythagorean_triplets([3, 1, 4, 6, 5]))

True

This code uses a single line of code to define find_pythagorean_triplets(). We generate a set of squares and use any() to check if there’s at least one pair (a, b) whose sum of squares is in the set of squares.

Bonus One-Liner Method 5: Pythonic Set Comprehension

For Python enthusiasts, a more succinct one-liner combines set comprehension and the itertools.combinations() function, retaining an average O(n^2) time complexity.

Here’s an example:

from itertools import combinations

def find_pythagorean_triplets(lst):
    return any(a**2 + b**2 == c**2 for a, b, c in combinations(lst, 3))

# Test the function
print(find_pythagorean_triplets([3, 1, 4, 6, 5]))

True

This one-liner uses combinations() from the itertools module to generate all possible triplets and checks each for the Pythagorean condition. It is elegant and uses Python’s powerful standard library.

Summary/Discussion

  • Method 1: Brute Force Approach. Simple to understand but inefficient for large lists with high time complexity.
  • Method 2: Sorting and Binary Search. More efficient than brute force by utilizing sorting and binary search but still involves relatively complex logic.
  • Method 3: Hashing. Significantly improves performance with average O(n^2) complexity and is straightforward to implement.
  • Method 4: List Comprehension and Any Function. Pythonic and concise but does not improve on the hashing method’s complexity.
  • Bonus Method 5: Pythonic Set Comprehension. Elegant one-liner for Python enthusiasts, uses powerful itertools but does not improve complexity.