-4

I need to know whether the elements in the list satisfies the condition a*a + b*b = c*c, where a, b and c are any elements in the following list:

original_list =[8,5,73,3,34,4,23,73]

Mathematically, 3*3 + 4*4 = 5*5, but not sure how to traverse the list in python to satisfy that condition.

Blckknght
  • 100,903
  • 11
  • 120
  • 169
Deba G
  • 9
  • 1

3 Answers3

2

You can iterate over the items from your list using itertools.combinations:

import itertools

for a, b, c in itertools.combinations(sorted(original_list), 3):
    if a*a + b*b == c*c:
        print("Pythagorean triple found:", a, b, c) # or whaver...

Note that I sort the original list before passing it to combinations. That ensures that a <= b <= c. While we don't really care about the relative order of a and b, but the fact that c is no smaller than either of them is a prerequisite for the test you're doing.

Blckknght
  • 100,903
  • 11
  • 120
  • 169
  • Nice approach, but note that this may not work as expected if the list contains numbers less than 1. – Mazdak May 31 '18 at 21:55
  • @Kasramvd: Hmm, good point. Sorting with `key=abs` should do the trick, I think, though I suspect negatives are unlikely to be valid inputs. – Blckknght May 31 '18 at 21:59
  • Just edited the comment by changing the "negative" to "less than one" :) but yes. If it's integer using `key=abs` will do the trick other wise maybe a more complicated key function that can also handles the situations like `0.5 * 0.5 + 0.1 * 0.1 == 0.26`. – Mazdak May 31 '18 at 22:00
  • This has really bad complexity; I don't know the formula but I ran couple tests: time python -c ' from itertools import combinations i = 0 for a, b, c in combinations(range(1000), 3): i += 1 print(i)' 166167000 python -c 15.44s user 0.01s system 99% cpu 15.466 total – jyn May 31 '18 at 22:10
  • with better formatting: `python -m timeit -n 1 -s 'from itertools import combinations; i = 0' 'for a, b, c in combinations(range(1000), 3): i+=1' 'print(i)'` `1 loops, best of 3: 8.43 sec per loop` – jyn May 31 '18 at 22:21
1

This questions revolves more around math and algorithms than pythonisms. The solution I propose below has a complexity in O(n**2).

The idea is to reverse the function (x, y) => x * x + y * y, where the search space is the cross product of the original list with itself. Then, using Python set operators, compute the intersection between the application image and the acceptable squares. Eventually, use the reversed application to reconstruct the triplets.

from collections import defaultdict

original_list = [8, 5, 73, 3, 34, 4, 23, 73]
uniq = sorted(set(original_list))

antecedents = defaultdict(lambda: []) # Reverse mapping
for i, left in enumerate(uniq):
    for right in uniq[i+1:]:
        key = left * left + right * right
        antecedents[key].append((left, right))
# The keys of antecedents are sum of squares

uniq_squares = set([ x * x for x in uniq ])
common_keys = uniq_squares & antecedents.keys()

for key in common_keys:
    sqrt = int(0.5 + key**0.5)
    key_antecedents = antecedents[key]
    for (left, right) in key_antecedents:
        print("Found triplet:", (left, right, sqrt))
Mathieu CAROFF
  • 1,230
  • 13
  • 19
  • Can you explain that defaultdict to me? Is it creating a different empty list each time because python passes by reference? – jyn Jun 01 '18 at 00:02
  • @JoshuaNelson Python *never passes by reference* – juanpa.arrivillaga Jun 01 '18 at 00:10
  • 1
    Note you can just do `defaultdict(list)` since `list()` already returns `[]` – juanpa.arrivillaga Jun 01 '18 at 00:12
  • `>>> a = {}` `>>> def f(d):` `... d['test'] = True` `... ` `>>> f(a)` `>>> a['test']` True – jyn Jun 01 '18 at 00:15
  • ahh I see why I was confused, `defaultdict` requires a `__call__`able function, not a value – jyn Jun 01 '18 at 00:20
  • 1
    @JoshuaNelson this does not demonstrate call by reference semantics. This would: `>>> a = 'foo'` `>>> def f(&x):` `... x = 'bar'` `... >>> f(a)` `>>> a` `'bar'` The key point is that *assignments to the reference are seen by the caller*. – juanpa.arrivillaga Jun 01 '18 at 09:21
  • Thanks! I also used the idea to have the squares in another list and find the triplets . import math number_list = [7,3,8,10,18,5,2,4] number_list2=[] for i in number_list: number_list2.append(i **2) for i in range(len(number_list2)): for j in range (i+1,len(number_list2)): if (number_list2[i]+ number_list2[j]) in number_list2: print((number_list2[i],number_list2[j],number_list2[i]+ number_list2[j])) print(((math.sqrt(number_list2[i]),(math.sqrt(number_list2[j])),(math.sqrt(number_list2[i]+ number_list2[j]))))) – Deba G Jun 06 '18 at 04:48
0

Python code

[(a,b,c) for a in original_list for b in original_list for c in original_list if a*a+b*b==c*c]

Output:

[(3, 4, 5), (4, 3, 5)]
Miguel Garcia
  • 356
  • 1
  • 5
  • Try doing that with a list longer than 10 numbers. – jyn May 31 '18 at 23:59
  • If ram is a problem you can use generators instead of lists `((a,b,c) for a in original_list for b in original_list for c in original_list if a*a+b*b==c*c)` – Miguel Garcia Jun 02 '18 at 04:18