;; Generate Pythagorean triples using combinations. (1.03)
;; @see Yn3fZb

(use-modules (srfi srfi-1)   ; pair-fold-right
             (srfi srfi-67)  ; list-compare
             (ice-9 format)) ; advanced formatting

;; Combinations.

(define (pair-map proc l)
  (pair-fold-right (lambda (item init)
                     (cons (proc item) init))
                   '() l))

(define (pair-append-map proc l)
  (apply append (pair-map proc l)))

(define (combinations sequence k)
  (if (zero? k)
      (list '())
      (pair-append-map (lambda (rest)
                         (map (lambda (comb)
                                (cons (car rest) comb))
                              (combinations (cdr rest) (- k 1))))
                       sequence)))

;; Pythagorean triples.

(define (primitive-pythagorean-triple? x y z)
  (and (< x y z)
       (= (+ (* x x) (* y y)) (* z z))
       (= (gcd x y z) 1)))

(define (pythagorean-triples n)
  (filter-map (lambda (v)
                (apply (lambda (x y z)
                         (if (primitive-pythagorean-triple? x y z)
                             v
                             #f))
                       v))
              (combinations (iota n 1) 3)))

;; Main.

(define (list-less-reverse x y)
  (< (list-compare (reverse x) (reverse y)) 0))

(for-each (lambda (v)
            (format #t "(~{~2D~^ ~})~%" v))
          (sort (pythagorean-triples 97) list-less-reverse))