a função haskell: pytrique escrevi é uma compreensão que recebe um valor inteiro n como entrada e retorna uma lista de todos os triplos (a, b, c) com a, b, c ≤ n que satisfazem o teorema de Pitágoras: 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 ]
No entanto, contém todas as permutações desses triplos, por exemplo:
pytri 10 == [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
Mas deveria ser:
pytri 10 == [(5,4,3),(10,8,6)]
Como posso remover a permutação adicional e classificá-las internamente em ordem decrescente?
Você deve quebrar a simetria. Como sabemos que b e c sempre podem ser trocados, quebramos a simetria com uma restrição extra de que a≤b :
também podemos limitar a busca
cfacilmente, aumentando a eficiência:Podemos fazer truques extras para procurar
cde forma mais eficaz e limitar o “espaço” em que procuramosaeb, deixo isso como exercício.