3

I need to find all the "a" and "b" values for a Pythagorean triple. For example, I would specify the number as a parameter and find all the Pythagorean triples for it. Here is some example code that my teacher gave me:

>>> pytriples(5)
>>> [3,4,5] #would return this
>>> pytriples(25)
>>> [7,24,25] #would return this
>>> [15,20,25] #would return this

Basically, I need to write the pytriples program and I get full marks for not having repeats of "a" and "b". This is what I have developed - the problem is, I do not have any way to remove the duplicates.

This is what I have:

def pytriples(c):
    newlist = []
    for a in range(0, c):
        if ((c**2 - a**2)**0.5)%1 == 0:
            b = ((c**2 - a**2)**0.5)
            newlist.append([a,b,c])
    for i in newlist: #this part is supposed to remove the duplicates
        print i[0] #was used for debugging but I could not figure out why duplicates were not removed
        if i[0] >= i[1]:
            newlist.remove(i)
    return newlist
Nathan
  • 4,009
  • 2
  • 20
  • 21
Alex Mann
  • 752
  • 6
  • 11
  • 3
    go through this http://stackoverflow.com/questions/575117/generating-unique-ordered-pythagorean-triplets – avasal Dec 07 '12 at 03:30

6 Answers6

1

Not sure if this is what you want..

you can remove the duplicates from a list of tuples of triplets like

consider you got all the triplets in list l

In [39]: l
Out[39]: [(1, 2, 3), (2, 3, 4), (2, 1, 3)]

to remove all the duplicates from this you can use 

In [40]: set(map(tuple, [sorted(x) for x in l]))
Out[40]: set([(2, 3, 4), (1, 2, 3)])

you can then convert it to list for further processing

In [41]: list(set(map(tuple, [sorted(x) for x in l])))
Out[41]: [(2, 3, 4), (1, 2, 3)]

in your case,

It's a bad idea to modify the list you are iterating within the loop,

since as soon as you remove suppose item1, item2 becomes item1 but loop has already iterated item1 in list so that check will be skipped and you will not get the desired output

consider a small example

In [43]: l
Out[43]: [(1, 2, 3), (2, 3, 4), (2, 1, 3)]

In [44]: for i in l:
   ....:     if i[0] == 2:
   ....:         l.remove(i)
   ....:

In [45]: l
Out[45]: [(1, 2, 3), (2, 1, 3)]
avasal
  • 14,350
  • 4
  • 31
  • 47
  • While using `set()` is generally a good method for removing duplicates, the fact that we have information about the structure of duplicates, in this case (`triplet[0] >= triplet[1]`), might make the list comprehension approach faster. +1, though. :) – Eric O. Lebigot Dec 07 '12 at 03:40
  • I haven't learned about that yet, but from my code, I just need to know why it is not removing list elements with the for loop. – Alex Mann Dec 07 '12 at 03:52
  • @AlexMann: It's a bad idea to modify the list you are iterating within the loop, instead just create a different list append the required values to it in the loop then return/print – avasal Dec 07 '12 at 03:56
0

Modifying a list while iterating over it is to be avoided.

Removing elements the way you want can be achieved with a simple list comprehension:

newlist = [triplet for triplet in newlist if triplet[0] < triplet[1]]
Eric O. Lebigot
  • 91,433
  • 48
  • 218
  • 260
  • Using a `set` instead might be even simpler. – 9000 Dec 07 '12 at 03:32
  • `set` is not bad, but requires sorting the triplets. I guess the `set` approach is slower, for this reason and because it does not use the fact that we know what duplicates look like (`triplet[0] >= triplet[1]`). – Eric O. Lebigot Dec 07 '12 at 03:42
0

Instead of putting duplicates into the array and then using a pass to take them back out, just don't put them into it in the first place. You could change

        newlist.append([a,b,c])

to

        if a<b: newlist.append([a,b,c])

and delete all of the for i in newlist: loop and its contents.

(Note, a cannot equal b because sqrt(2) is irrational.)

James Waldby - jwpat7
  • 8,593
  • 2
  • 22
  • 37
0

Instead of doing a full scan, I'd rather pre-calculate enough triplets and try to find a match. If all numbers are smaller than the given one, I'd calculate more on the fly :)

Your algorithm has a correct idea, but can be implemented simpler. Some basic trigonometry rids you of duplicates completely.

def pytriplets(hypotenuse):
    result = []
    # we only need to check half the triangles,
    # the rest are the same triangles with catheti swapped.
    # 0.71 is approximated sin(pi / 4). Biggest possible catheti are
    # in the isosceles triangle; no bigger should ever be checked. 
    # +1 is because range() excludes the top bound. 
    for a in range(1, int(hypotenuse * 0.71) + 1):
        hypo_squared = hypotenuse * hypotenuse
        a_squared = a * a
        # Square root will give us slight approximation errors;
        # explicitly make our other cathetus integer.
        b = int((hypo_squared  - a_squared) ** 0.5)
        if a_squared + b*b == hypo_squared:
            # A perfect match!
            result.append((hypotenuse, a, b)) # appending a tuple
    return result

print pytriplets(5)
print pytriplets(25)
Roman Pokrovskij
  • 9,449
  • 21
  • 87
  • 142
9000
  • 39,899
  • 9
  • 66
  • 104
0

I generate the list of all perfect squares below c and with two pointers from both ends of the list i'll try to find the pairs which of numbers which sum to c^2 until they cross over.

def pythogorian_triplets(c):
    c_square = c ** 2
    #list of perfect squares below c_square
    squares = [1]
    #populating the list
    for i in range(1, c - 1):
        squares.append(squares[-1] + (i << 1) + 1)

    i = 0
    j = c - 2
    l = c - 1

    while j >= i and i < l:
        while (squares[i] + squares[j] < c_square) and i < l and j > i:
            i = i + 1
        if squares[i] + squares[j] == c_square:
            print (i + 1, j + 1, c)
        j = j - 1

if __name__ == '__main__':
    pythogorian_triplets(int(raw_input()))
Harish Tummalacherla
  • 388
  • 3
  • 10
0

import math

def main(): for x in range (1, 1000): for y in range (1, 1000): for z in range(1, 1000): if x*x == y*y + z*z and x+y+z ==1000: print y, z, x print '-'*50

if name == 'main': main()

niraj
  • 11
  • 2