SICP 問題 2.40（全ての相異なる数字による組合わせを求める）

問題

与えられた整数 n に対し、1≦j＜i≦n の対 (i, j) の並びを生成する手続き unique-paires を定義せよ。unique-pairs を使って、上の prime-sum-paires の定義を簡単にせよ。

解答

まずは　unique-paires から。
「与えられた整数 n に対し、1≦j＜i≦n の対 (i, j) の並びを生成する」んだから、例えば 1〜4 ならこんな対データがとれればOK。

((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

各対の先頭の数字を基準に考えると、もう一つの数字はそれより大きい数字で構成される。こんな感じで map かけていけば良いんじゃない？

(1                   2             3       4 )
;↓map
(((1 2) (1 3) (1 4)) ((2 3) (2 4)) ((3 4)) ())
;↓accumulate（appendを使用）
( (1 2) (1 3) (1 4)   (2 3) (2 4)   (3 4)    )

では順番に考えていこう。
最初の (1 2 3 4) は、enumerate-intervalを使えばすぐに生成できる。

gosh> (enumerate-interval 1 4)

(1 2 3 4)

gosh> 

これに map を適用して次の段階のリストにするには、こんな感じ。

(map (lambda (x)
       ;1 → ((1 2) (1 3) (1 4))
       ;2 → ((2 3) (2 4))
       ;3 → ((3 4))
       ;4 → ()
       ;にするような手続き
       )
     (enumerate-interval 1 4))

コメントの部分を考えると、更に enumerate-interval と map を使って実現できる。

(map (lambda (x)
       (map (lambda (y)
	      ;x よりも１つ大きい数字を先頭としたリストを生成し、
	      ;そのリストを対の後ろの要素とするリストを返す。
              ;実際にはこんな変換になる。
              ;(2 3 4) → ((1 2) (1 3) (1 4))
              ;(3 4)   → ((2 3) (2 4))
              ;(4)     → ((3 4))
	      (list x y))
	    (enumerate-interval (+ x 1) 4)))
     (enumerate-interval 1 4))

こいつを評価するとこんな感じになってくれる。

gosh> (((1 2) (1 3) (1 4)) ((2 3) (2 4) ) ((3 4) ) () )

gosh> 

更にこれに accumulate/append を適用してやるとこんな感じ。

(accumulate append
	    '()
	    (map (lambda (x)
		   (map (lambda (y)
			  (list x y))
			(enumerate-interval (+ x 1) 4)))
		 (enumerate-interval 1 4)))

gosh> ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4) )

gosh> 

あとは、今決め打ちにしている 1 とか 4 を外から渡してやれば unique-paires のできあがり。

(define (unique-paires j i)
  (accumulate append
	      '()
	      (map (lambda (x)
		     (map (lambda (y)
			    (list x y))
			  (enumerate-interval (+ x 1) i)))
		   (enumerate-interval j i))))

では実験。

gosh> (unique-paires 1 4)

((1 2) (1 3) (1 4) (2 3) (2 4) (3 4) )

gosh> 

よしよし。

次に unique-pairs を使って、prime-sum-paires の定義を簡単にせよとのこと。
で、prime-sum-paires は何かというと、この問題の直前にあるセクションで定義されている手続きなので、ここに掲載しておこう。

;件の手続き
(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)))))


;件の手続きが必要とする手続き群
(use srfi-1) ;filter手続きの為に必要。

(define (make-pair-sum pair)
  (let ((i (car pair))
	(j (cadr pair)))
    (list i j (+ i j))))

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

(define (prime? n)
  (= n (smallest-divisor n)))

(define (smallest-divisor n)
  (find-divisor n 2))
　
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (square x)
  (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

要するに、filter 手続きに unique-paires で生成した対を渡してやればいいわけだ。こんな感じに。

;新しい prime-sum-pairs の定義
(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
	       (unique-paires 1 n))))

では実験。

gosh> (prime-sum-pairs 4)

((1 2 3) (1 4 5) (2 3 5) (3 4 7) )

gosh> (prime-sum-pairs 5)

((1 2 3) (1 4 5) (2 3 5) (2 5 7) (3 4 7) )

gosh> (prime-sum-pairs 6)

((1 2 3) (1 4 5) (1 6 7) (2 3 5) (2 5 7) (3 4 7) (5 6 11) )

gosh> 

合ってるね。
以前年賀状の宛名印刷ツールを改訂したときも思ったけど、map とか filter って便利だよな。。
ちなみにSICPの注釈に書いてあったんだけど、とある FORTRAN プログラムを解析した結果、その９０％が map と filter で代替可能なロジックだったとかなんとか。
そーいえばUNIX上で使うシェルスクリプトなんかほとんどデータ変換とデータ抽出だもんな。CでUNIXのプログラム書くときも、パイプでコマンドを連結できるように書くべしとかいう格言があったし。
GUIとかはまぁ置いておいても、プログラム設計の一つの指針にはなるのだろう。