SICP q2.41

gistfile1.scm

; 1 <= k < j < i <= n
;
; e.g.) 
; s = 6
; 1 + 2 + 3 = 6
;
; s = 7
; 1 + 2 + 4 = 7
; 
; s = 8
; 1 + 2 + 5 = 8
; 1 + 3 + 4 = 8
; 
; s = 9
; 1 + 2 + 6 = 9
; 1 + 3 + 5 = 9
; 
; s = 10
; 1 + 2 + 7 = 10
; 1 + 3 + 6 = 10
; 1 + 4 + 5 = 10
; 2 + 3 + 5 = 10
;
; 方針
; まず、
; 1 <= k < j < i <= n
; なる(i j k)の並びの一覧を全て作り、
; そのあと和がsになるような並びだけになるようにfilterすれば良さそう
;
; 最終的な呼び出し方は
; (define n 10)
; (define s 6)
; (make-s n s)
; みたいな感じでいいのかな

; 必要となりそうなdefineをとりあえず書いておく
; nil
(define nil '())
; 1ずつ増えるような数列
(define (enumerate-interval low high)
  (if (> low high)
    nil
    (cons low (enumerate-interval (+ low 1) high))))
; listを作るaccumulate
(define (accumulate op initial sequence)
  (if (null? sequence)
    initial
    (op (car sequence)
        (accumulate op initial (cdr sequence)))))

; まず、
; 1 <= k < j < i <= n
; なる(i j k)の並びの一覧を全て作るので、
; p.71のaccumulateを参考に(list i j k)となるようにする
;
; (1 2 3 4 5)
;  | (enumerate-interval 1 (- i 1)) のmapでlist内listができたから
; (() (2 1) ((3 1) (3 2)) ((4 1) (4 2) (4 3)) ((5 1) (5 2) (5 3) (5 4)))
;  | (enumerate-interval 1 (- j 1)) のmapでさらにlist内listができる
; (() (()) (() ((3 2 1))) (() ((4 2 1)) ((4 3 1) (4 3 2))) (() ((5 2 1)) ((5 3 1) (5 3 2)) ((5 4 1) (5 4 2) (5 4 3))))
; あとはこれをflatにすればいい
;
; まず、3つの並びにするのは
;
; (map (lambda (i)
;        (map (lambda (j)
;               (map (lambda (k) (list i j k))
;                    (enumerate-interval 1 (- j 1))))
;             (enumerate-interval 1 (- i 1))))
;      (enumerate-interval 1 n))
;
; これをflatにしたいのでp.71の

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

; を使ってmapをflatmapに変える
;
; (flatmap (lambda (i)
;        (flatmap (lambda (j)
;               (map (lambda (k) (list i j k))
;                    (enumerate-interval 1 (- j 1))))
;             (enumerate-interval 1 (- i 1))))
;      (enumerate-interval 1 n))

; 次にfilterを作る
; (define s 6)
; (s-sum? (list 1 2 3) s)
; みたいなのがあれば良さそう
;
; listの数の足し算はaccumulate使ってcount-leavesを思い出してsum-leavesを作ればいいかな
(define (sum-leaves t) (accumulate + 0 t))

; そうするとs-sum?はsとsum-leavesの比較なので
(define (s-sum? seq s) (= s (sum-leaves seq)))

; ただ、make-sの外でs-sum?をdefineするとsが外に出るのが何となく嫌なのでlambdaでいいかも
; ということで、あとはこれらをまとめて
(define (make-s n s)
  (filter (lambda (seq) (= s (sum-leaves seq)))
          (flatmap (lambda (i)
                     (flatmap (lambda (j)
                                (map (lambda (k) (list i j k))
                                     (enumerate-interval 1 (- j 1))))
                              (enumerate-interval 1 (- i 1))))
                   (enumerate-interval 1 n))))


(define n 10)
(print (make-s n 6)) ; ((3 2 1))
(print (make-s n 8)) ; ((4 3 1) (5 2 1))