5 Best Ways to Check Triangular Inequality on List of Lists in Python

💡 Problem Formulation: This article addresses the challenge of verifying the triangular inequality in a list of lists in Python. The triangular inequality theorem states that, for any triangle, the sum of the lengths of any two sides must be greater than the third side. Given a list of lists, where each list represents the lengths of the sides of a potential triangle, the task is to determine if each set of sides satisfies this condition. For example, given input [[3, 4, 5], [1, 2, 3]], the desired output would be [True, False], indicating that only the first list of sides forms a valid triangle.

Method 1: Iterative Triangular Inequality Check

This method employs a simple iterative approach, comparing each set of three side lengths within the list of lists. A function check_triangles is defined that takes the list of lists as input, iterates through each sublist, and checks for triangular inequality by ensuring that the sum of any two side lengths is greater than the third side.

Here’s an example:

def check_triangles(triangle_sides):
    results = []
    for sides in triangle_sides:
        sides.sort()
        if sides[0] + sides[1] > sides[2]:
            results.append(True)
        else:
            results.append(False)
    return results

print(check_triangles([[3, 4, 5], [1, 2, 3]]))

Output: [True, False]

This code snippet first defines a function check_triangles that sorts each sublist to guarantee the correct order of side lengths. It then checks the triangular inequality rule against each set of sides. The results list captures whether each set of sides passes or fails the check, which is printed at the end of the script.

Method 2: Using List Comprehension

This method streamlines the checking process using list comprehension. List comprehension is a succinct way to apply an expression to each item of an iterable, transforming it into a list. The method takes the list of lists and applies the triangular inequality check in a single line of code within the comprehension.

Here’s an example:

def check_triangles(triangle_sides):
    return [True if sides[0] + sides[1] > sides[2] else False for sides in (sorted(side_lengths) for side_lengths in triangle_sides)]

print(check_triangles([[3, 4, 5], [1, 10, 12], [2, 2, 2]]))

Output: [True, False, True]

The function check_triangles now uses list comprehension, running a sorted operation on each sublist before performing the check. The single line of code within the function makes it more concise yet maintains readability. The result is a list representing the validity of each set of sides accordingly.

Method 3: Using all() Function

The use of the all() function provides a way to check if all conditions within the iterable are True. It simplifies the iteration and checking process by evaluating conditions in sequence until it encounters the first False statement.

Here’s an example:

def check_triangles(triangle_sides):
    return [all([sides[i] + sides[j] > sides[k] for i, j, k in permutations(range(3), 3) if i < j]) for sides in triangle_sides]

from itertools import permutations
print(check_triangles([[3, 4, 5], [1, 2, 3], [10, 15, 7]]))

Output: [True, False, True]

This function leverages Python’s all() function in conjunction with a list comprehension and the permutations function from the itertools module. This checks all permutations of sides to affirm the triangular inequality. It effectively checks each condition without the need for sorting and is efficient for larger lists.

Method 4: Using a Generator Expression

Generator expressions are a high-performance, memory-efficient generalized iteration mechanism. Similar to list comprehensions, generator expressions are more space-efficient since they yield items one by one using the iterator protocol instead of creating a temporary list.

Here’s an example:

def check_triangle_gen(triangle_sides):
    return list(all(sides[i] + sides[j] > sides[k] for i, j, k in permutations(range(3), 3) if i < j) for sides in triangle_sides)

from itertools import permutations
print(check_triangle_gen([[3, 4, 5], [1, 2, 3]]))

Output: [True, False]

The function check_triangle_gen applies a generator expression similarly to the previous method, but without creating intermediate lists, making it more memory-efficient. A generator object is created for each set of sides, evaluated by the all() function, and the results are then converted to a list with the desired True/False values.

Bonus One-Liner Method 5: Using map() and lambda

A one-liner approach employs the map() function alongside a lambda function to apply the check across all sublists concisely. The map function applies the lambda to every item of the iterable (the list of lists).

Here’s an example:

triangle_sides = [[3, 4, 5], [1, 2, 3]]
check_triangle = map(lambda sides: sides[0] + sides[1] > sides[2], (sorted(s) for s in triangle_sides))
print(list(check_triangle))

Output: [True, False]

This one-liner uses map() to apply a lambda function that checks the inequality over a generated sequence of sorted side lengths. It results in a map object containing boolean values corresponding to each set of sides, which is then converted into a list for easier readability.

Summary/Discussion

• Method 1: Iterative Triangular Inequality Check. Strengths: Straightforward and easy to understand. Weaknesses: Not the most efficient in terms of lines of code or performance.
• Method 2: Using List Comprehension. Strengths: More concise and Pythonic. Weaknesses: Slightly less clear for beginners.
• Method 3: Using all() Function. Strengths: Compact and efficient for larger lists. Weaknesses: May be difficult to grasp for those unfamiliar with permutations and the all() function.
• Method 4: Using a Generator Expression. Strengths: Space-efficient for very large lists. Weaknesses: Creates a generator object that needs to be converted to a list if needed.
• Bonus Method 5: Using map() and lambda. Strengths: Extremely succinct and performs well. Weaknesses: Can be cryptic and reduce code readability.