Тройка Пифагора в Хаскеле без симметричных решений

Question

Я должен сделать тройку Пифагора в Хаскеле без симметричных решений. Моя попытка:

terna :: Int -> [(Int,Int,Int)]
terna x = [(a,b,c)|a<-[1..x], b<-[1..x], c<-[1..x], (a^2)+(b^2) == (c^2)]

и в результате я получаю:

Main> terna 10
[(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

Как видите, я получаю симметричные решения вроде: (3,4,5) (4,3,5) Мне нужно от них избавиться, но я не знаю как. Кто-нибудь может мне помочь?

Answer 1

Каждый раз, когда у вас есть дубликат, у вас есть одна версия, в которой a больше, чем b, и одна, где b больше, чем a. Поэтому, если вы хотите быть уверенным, что получите только один из них, вам просто нужно убедиться, что либо a всегда равно или меньше b, либо наоборот.

Один из способов добиться этого - добавить его в качестве условия для понимания списка.

Другой, более эффективный способ - изменить генератор b на b <- [1..a], поэтому он генерирует только значения для b, которые меньше или равны a.

Кстати, об эффективности: нет необходимости перебирать c. Если у вас есть значения для a и b, вы можете просто вычислить (a^2)+(b^2) и проверить, имеет ли он естественный квадратный корень.

Answer 2

Совсем не знаю Haskell (возможно, вы изучаете его сейчас?), Но кажется, что вы могли бы избавиться от них, если бы вы могли взять только те, для которых a меньше или равно b. Это избавило бы от дубликатов.

Answer 3

Попробуйте с помощью простого рекурсивного генератора:

http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples

(новая статья)
http://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples

РЕДАКТИРОВАТЬ (7Май 2014)

Здесь я создал бесконечный генератор, который может генерировать примитивные триплеты, упорядоченные по периметру (но могут быть изменены, чтобы упорядочить их по другому параметру - гипотенузы, площадь, ...), если он считает, что любойтриплет меньше, чем любой генерируемый из матрицы генератора в соответствии с предоставленной функцией сравнения

import Data.List -- for mmult

merge f x [] = x
merge f [] y = y
merge f (x:xs) (y:ys)
               | f x y     =  x : merge f xs     (y:ys) 
               | otherwise =  y : merge f (x:xs) ys 


mmult :: Num a => [[a]] -> [[a]] -> [[a]] 
mmult a b = [ [ sum $ zipWith (*) ar bc | bc <- (transpose b) ] | ar <- a ]

tpgen_matrix = [[[ 1,-2, 2],[ 2 ,-1, 2],[ 2,-2, 3]],
                [[ 1, 2, 2],[ 2 , 1, 2],[ 2, 2, 3]],
                [[-1, 2, 2],[-2 , 1, 2],[-2, 2, 3]]]

matrixsum  =  sum . map sum
tripletsorter x y =  ( matrixsum  x ) < ( matrixsum y ) -- compare perimeter

triplegen_helper b =  foldl1 
            ( merge tripletsorter ) 
            [ h : triplegen_helper h | x <- tpgen_matrix , let h = mmult x b ]

triplets =  x : triplegen_helper x  where x = [[3],[4],[5]]

main =  mapM print $ take 10 triplets

Answer 4

Это может работать: Получено из этого урока

triangles x = [(a,b,c) | c <- [1..x], b <- [1..c], a <- [1..b] , a^2 + b^2 == c^2]  

Answer 5

Вы можете сделать следующее:

pythagorean = [ (x,y,m*m+n*n) | 
                                m <- [2..], 
                                n <- [1 .. m-1], 
                                let x = m*m-n*n, 
                                let y = 2*m*n ]