SICPを読む(58) 2.2.3(2) 写像の入れ子 と 問題 2.40 - 2.41

Scheme

順列の問題です。頭の中が混乱した。

話題の中心は

mapをfor文のように使ってみてはどうだろうかという話題らしい。

混乱したのは問題の定義

混乱したところを分割して読むと。

  • 与えられた整数nに対して
  • 1<= j < i <= nである
  • 正の整数(i, j)
  • i + jが素数になるもの。

「j < i で、(i, j)」ってiとjが逆じゃないか!!

と随分たってから気づいた。

素数について。

疑問

removeで(not (= x item))と指定したものを取り除いている。リストがユニークな場合はこれでいいと思う。もしも内容がユニークでない場合、removeだとおかしな事になってしまう。

(1 2 2 3 3 3)というリストだった場合、3を取り除くと、(1 2 2)になってしまう。

n番目の要素を取り除くように、インデックスで判断したほうが良さげな気がする。

問題 2.40

必要な要素を抜き出せば良い。

(define (unique-pairs n)
  (flatmap (lambda (i)
             (map (lambda (j)
                    (list i j))
                  (iota (- i 1) 1)))
           (iota n 1)))

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

問題 2.41

まずは、unique-pairsの3個版。

(define (unique-trio n)
  (flatmap (lambda (i)
      (flatmap (lambda (j)
          (map (lambda (k) (list i j k))
               (iota (- j 1) 1)))
        (iota (- i 1) 1)))
    (iota n 1)))

(define (unique-trio n)
    (flatmap (lambda (i)
               (map (lambda (j) (cons i j))
                    (unique-pairs (- i 1))))
      (iota n 1)))

(map reverse (unique-trio 4)) ; ((1 2 3) (1 2 4) (1 3 4) (2 3 4))

上は最初に作った奴。下はunique-pairsを利用したもの。

(map reverse)を使うと見やすくできます。

これを使ってフィルタを通します。

(define (trio-filter-sumeq n sum)
  (filter (lambda (i)
            (= sum (+ (car i) (cadr i) (caddr i))))
    (unique-trio n)))

(map reverse (trio-filter-sumeq 10 12)) ; ((3 4 5) (2 4 6) (1 5 6) (2 3 7) (1 4 7) (1 3 8) (1 2 9))

いい感じ。

まとめ

(i, j, k)は i < j < kの方がわかりやすい。