可以分为两个步骤

1. 生成三元组序列
2. 过滤这个三元组序列，得到加和的结果为指定 s 的三元组

这个题的难点在于产生一个不重复的、有序的三元组。在上一题中，我们已经通过两个循环（map）产生出了所有不重复的、有序的二元组。

(load "33-accumulate.scm")

(define nil '())

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

(define (prime? n)
  (define (divide? a b)
    (= (remainder a b) 0))
  (define prime-rec?
    (let ((maxone (sqrt n)))
      (lambda (x)
        (cond ((> x maxone) #t)
              ((divide? n x) #f)
              (else (prime-rec? (+ 1 x)))))))
  (prime-rec? 2))

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap (lambda (i)
                          (map (lambda (j) (list i j))
                               (enumerate-interval 1 (- i 1))))
                        (enumerate-interval 1 n)))))

;;; unique-pairs
(define (unique-pairs n)
  (flatmap
   (lambda (i)
     (map (lambda (j) (list i j))
          (enumerate-interval 1 (- i 1))))
   (enumerate-interval 1 n)))

(define (simplified-prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (unique-pairs n))))

我们利用三个循环（map）呢？我们有两种方法来产生不重复的且有序的三元组。

第一种，对 (i, j, k) 中的每一位进行 1-n 的遍历，然后去掉重复的元组。

(define (unique-triples-1 n)
  (define (unique-triple? triple)
    (let ((a (car triple))
          (b (cadr triple))
          (c (caddr triple)))
      (if (or (= a b) (= a c) (= b c))
          #f
          #t)))
  (filter unique-triple?
          (flatmap
           (lambda (i)
             (flatmap (lambda (j)
                        (map (lambda (k)
                               (list i j k))
                             (enumerate-interval 1 n)))
                      (enumerate-interval 1 n)))
           (enumerate-interval 1 n))))

结果为：

(unique-triples-1 4)

;Value 10: ((1 2 3) (1 2 4) (1 3 2) (1 3 4) (1 4 2) (1 4 3) (2 1 3) (2 1 4) (2 3 1) (2 3 4) (2 4 1) (2 4 3) (3 1 2) (3 1 4) (3 2 1) (3 2 4) (3 4 1) (3 4 2) (4 1 2) (4 1 3) (4 2 1) (4 2 3) (4 3 1) (4 3 2))

第二种方法，规定 (i, j, k) 的大小为 i < j < k ，产生的三元组再通过置换来达到遍历的效果。

所以第一步中生成三元组序列，应该分为两部分：

1. 1.1 生成不重复的三元组表
2. 1.2 对其中的每个三元组进行置换

(define (permutations s)
  (if (null? s)                    ; empty set?
      (list nil)                   ; sequence containing empty set
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

(define (unique-triples-2 n)
  (flatmap permutations
           (flatmap (lambda (i) ; generate (i, j, k) so that i < j < k
                      (flatmap (lambda (k)
                                 (map (lambda (j)
                                        (list i j k))
                                      (enumerate-interval (+ 1 i) (- k 1))))
                               (enumerate-interval (+ 2 i) n)))
                    (enumerate-interval 1 n))))

最后，实现过程 ordered-triples-sum 。其中 triple-sum 将对一个三元组进行求和，将和放到 car 的位置。

;;; find all ordered triples of distinct positive integers i, j, and k
;;; less than or equal to a given integer n that sum to a given
;;; integer s. 
(define (ordered-triples-sum n s)
  (define (triple-sum t)
    (let ((a (car t))
          (b (cadr t))
          (c (caddr t)))
      (cons (+ a b c) t)))
  (map (lambda (t-sum) (cdr t-sum))
       (filter (lambda (x) (= s (car x)))
               (map triple-sum
                    (unique-triples-1 n)))))