リスト修行 約数のリスト(2)
素因数分解まで出来ちゃいました、素因数分解から組み合わせ(部分集合の集合)を求めて再び約数に挑戦します。
組み合わせ
確か練習問題(2.32)にあったなぁと思いつつ。SICPをめくる。
あぁ、全然理解できなかった奴だ・・・。
頑張って理解しよう。ちょっと汚いけど、コメントしておく。
; 0. (subsets '(1 2 3))の時、 (define (subsets s) (if (null? s) ; 3. 最後まで辿り着いたら '(())を返して (list '()) ; 2. cdrダウン (let ((rest (subsets (cdr s)))) ; 4. 下から拾ってきたリストとappeed ; '(()) + (map 3をcons '()), ; '(() (3)) + (map 2をcons '(() (3)))) ; '(() (3) (2) (2 3)) + (map 1をcons '(() (3) (2) (2 3)))) ; '(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) 終了。 (append rest (map (lambda (x) ; 1. (car s) [1, 2, 3]を置いといて (cons (car s) x)) rest)))))
ふぅ。理解できた。
fold-rightを使って書き直してみる。
(define (subsets s) (fold-right (lambda (a b) (append b (map (lambda (x) (cons a x)) b))) '(()) s))
うっほ。セクシーに書けた。簡単だった。
組み合わせ(部分集合の集合)すると、
(factor 50) ; (2 5 5) (subsets (factor 50)) ; (() (5) (5) (5 5) (2) (2 5) (2 5) (2 5 5))
おぉぉぉ。これだよコレ。後は掛算すればいい。
約数を求める
最終章だ。最終章。やっと辿り着いた!!
(define (divisor n) (sort (unique (map (lambda (m) (fold * 1 m)) (subsets (factor n)))) <))
uniqueとsortを使って成形してっと。
50の約数を求めます。
(divisor 50) ; (1 2 5 10 25 50)
でたぁ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜約数だよ。約数。
大きい数もやってみよう。
(divisor 1000000) ; (1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 160 200 250 320 400 500 ; 625 800 1000 1250 1600 2000 2500 3125 4000 5000 6250 8000 10000 12500 ; 15625 20000 25000 31250 40000 50000 62500 100000 125000 200000 250000 ; 500000 1000000)
100万の約数だって一瞬で出る。はえぇぇぇよぉ。
