Remove permutations of tuples of a Pythagorean triple in haskell

Question

the haskell function: pytri that I have written is a comprehension that takes an integer value n as input and returns a list of all triples (a, b, c) with a, b, c ≤ n that satisfy the Pythagorean theorem: a2 = b2 + c2:

pytri :: Integer -> [(Integer,Integer,Integer)]
pytri n = [(a,b,c)| a <- [1..n],b<-[1..n],c<-[1..n], a^2+b^2==c^2 ]

However, it contains all permutations of these triples, e.g:

pytri 10 == [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

But should be instead:

pytri 10 == [(5,4,3),(10,8,6)]

How can I remove the additional permutation and sort them internally in descending order?

Answer 1

You should do symmetry breaking. Since we know that b and c can always be swapped, we break the symmetry with an extra constraint that a≤b:

pytri :: Integer -> [(Integer,Integer,Integer)]
pytri n = [(a,b,c)| a <- [1..n], b <- [a..n],c<-[1..n], a*a+b*b==c*c ]

we can also limit the search for c easily, boosting efficiency:

pytri :: Integer -> [(Integer,Integer,Integer)]
pytri n = [(a,b,c)| a <- [1..n], b <- [a..n],c<-[b..n], a*a+b*b==c*c ]

We can do extra tricks to look for c more effectively and limit the "space" in which we search for a and b, I leave that as an exercise.