SICP 問題 2.41（３つの数字の組合わせの全パターンを求める）

Scheme SICP

問題

与えられた整数 n に対して、n より小さいか等しい相異なる正の整数 i, j, k の順序付けられた三つ組で、和が与えられた整数 s になるものを全て見つけよ。

解答

前問の unique-paires を拡張して unique-3s とかにして、三つ組のリストを生成したのち、その和を求めて n になるかどうかという条件で filterかけてやる感じ。
では unique-3s について考えてみよう。
unique-paires は (a b) を要素とするリストを返したけど、今回は (a b c)を要素とするリストになるので、もう一段入れ子が必要になりそう。

(define (unique-3s n)
  (accumulate
   append
   '()
   (accumulate
    append
    '()
    (map (lambda (x)
	   (map (lambda (y)
		  (map (lambda (z)
			 (list x y z))
		       (enumerate-interval (+ y 1) n)))
		(enumerate-interval (+ x 1) n)))
	 (enumerate-interval 1 n)))))

３だけじゃなくて、 n 要素のに拡張できないかな。なんとなくパターンがあるし。

(define (unique-ns max length)
  ;リストの候補を生成する。
  (define (make-list len start ans)
    (map (lambda (i)
	   (if (= len 1)
	       (reverse (cons i ans))
	       (make-list (- len 1) max (+ i 1) (cons i ans))))
	 (enumerate-interval start max)))

  ;入れ子にっているリストをトップレベルに展開する
  (define (flat-list len src)
    (if (= len 1)
	src
	(flat-list (- len 1) (accumulate append '() src))))

  ;実行
  (flat-list length (make-list length n 1 '())))

・・・問題に書いてないけどやり始めたらドツボにハマった。。丸１日かかっちゃったよ。。
なんとかできたので実験。



gosh> (unique-ns 5 3)

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

gosh> (unique-ns 6 4)

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

gosh>
これで３つだけじゃなくて n 個の要素を持つリストに対しても適用可能になる。

さて、与えられた s と、各要素の和が等しくなるものだけを抽出するから、filter を使う。こんな感じか？

(define (equal-sum-pairs n l s)
  (filter (lambda (lis)
	    (= s (accumulate + 0 lis)))
	  (unique-ns n l)))

では実験。



gosh> (equal-sum-pairs 5 3 1)

()

gosh> (equal-sum-pairs 5 3 2)

()

gosh> (equal-sum-pairs 5 3 3)

()

gosh> (equal-sum-pairs 5 3 4)

()

gosh> (equal-sum-pairs 5 3 5)

()

gosh> (equal-sum-pairs 5 3 6)

((1 2 3) )

gosh> (equal-sum-pairs 5 3 7)

((1 2 4) )

gosh> (equal-sum-pairs 5 3 8)

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

gosh> (equal-sum-pairs 5 3 9)

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

gosh> (equal-sum-pairs 5 3 10)

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

gosh> (equal-sum-pairs 5 3 11)

((2 4 5) )

gosh> (equal-sum-pairs 5 3 12)

((3 4 5) )

gosh> (equal-sum-pairs 7 3 12)

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

gosh>
よさげ。