両替問題

両替問題の続きである. 前回の話題はSICPの再帰関数の解法であった. コンピュータの数学やPolyaの解法は, 母関数による. コンピュータの数学は, 「この問題はPolyaが母関数を用いて解くよい教材であることを示して, 一躍有名になった」と書く.

母関数

数列を閉じた式で表す摩可不思議な方法である. Fibonacci数は0,1,1,2,3,5,8,...であるが, The Art of Computer Programmingの1.2.8の式(11)には, その母関数がG(x)=x/(1-x-x²)であると書いてある. (元はxでなくzだが) これをばか正直に割ってみると, 商のx^nの係数がfib(n)になる. つまり無限数列0,1,1,2,3,5,8,...を「閉じた式」にしたものが母関数である.



日本語は母関数だが, 英語ではgenerating functionという. なにかを産み出すという意味で, 母関数という訳語は悪くない. 統計には母集団があり, 円柱や円錐には母線があり, 分数には分母があり, 音声には母音がある. 母国語もある. 航空母艦や潜水母艦や捕鯨母船もあるが, 残念にも父の出番はあまりない.

「閉じた式」にするとなにがいいか. 例えば1,1,1,1,...に1,1,1,1,...を掛けると1,2,3,4,...になりそうである. 一方 1,1,1,1,...は閉じた形では1+x+x²+x³+...=1/(1-x)である. 従って1,1,1,1,...掛ける1,1,1,1,...は
1/(1-x)*1/(1-x)=1/(1-2x+x²)
これをばか正直に割ってみると
1+2x+3x²+4x³+...
が得られる.

私も真面目に読んだのではないが, TAOCPの1.2.9項や, コンピュータの数学の7章(ともに母関数)のところは, そのうちきちんと読みたい.

そのもっとも入門的な使い方が, Polyaの講義ノートにある両替問題なので, 簡単に説明しよう.

1セント硬貨で1セント, 2セント, ...にする方法はどれも1通りなので,
1+x+x²+x³+x⁴...
のように書く. 最初の1は1セント硬貨をまったく使わない場合である.

5セントでは
1+x⁵+x¹⁰+x¹⁵+x²⁰...
xやx²の項は, 作れないから係数が0で, 省略してある.

これを10セント, 25セント, 50セントで書き, (1)式のように掛け合わせれば, x¹⁰⁰の係数のところに, 両替法の数が出るわけである.

(2)は1セントの可能性の式を閉じた形にしたもので, (1)の因子をすべて閉じた式にしたのが(3)である. 最後は(8)が欲しいのだが, それを求めるために, 1セントだけの式(4), 1セントと5セントだけの式(5), などを作る. (4)の係数Aはすべて1だから, それと(5)とからBが(9), (10)のように得られ, 順にC, D, Eが(11), (12), (13)のように得られる.

早速Schemeのプログラムを書く.

(define (a n) (if (< n 0) 0 1))
(define (b n) (if (< n 0) 0 (+ (a n) (b (- n 5)))))
(define (c n) (if (< n 0) 0 (+ (b n) (c (- n 10)))))
(define (d n) (if (< n 0) 0 (+ (c n) (d (- n 25)))))
(define (e n) (if (< n 0) 0 (+ (d n) (e (- n 50)))))

(e 100) => 292

(a b c d e)の呼ばれた回数は(292 332 49 12 4)であった.

メモ化すると(21 40 24 8 4)に減った.
メモ化にはalistを使った.

(define (e n) (set! ec (+ ec 1))
 (let ((x (assoc n ea)))
  (if x (cadr x)
   (let ((r (if (< n 0) 0 (+ (d n) (e (- n 50))))))
    (set! ea (cons (list n r) ea)) r))))

のように書いてある.

両替問題

研究所の山本君がSICP(Structure and Interpretation of Computer Programs)の両替問題がなんとかといっていたので, 両替問題をおさらいしよう. 英語ではchangeというので, Graham, Knuth, Patashnik著, 有澤他訳の「コンピュータの数学(Concrete Mathematics)」では, 「釣銭の問題」(299ページ)となっている. 正しくは, 空港のCHANGEの窓口と同じで, 外国のお金から, または高額のお金からの両替である. 数学の問題としては, 高額のお金の崩し方の話題である.

この問題はいろいろなところに書いてある. 前述のSICPや, コンピュータの数学の他, G. PolyaのHow to Solve It(如何にして問題を解くか)にもあり, 私がたまたま持っている, PolyaとTarjanの1978年のStanfordでの講義ノート, D.R.Woods, Notes on Introductory Combinatoricd(STAN-CS-79-732)にも出ている.

SICPの記述はこうだ

50セント, 25セント, 10セント, 5 セント, 1セントがあるとして1ドルの両替にはどのくらいの場合があるか. つまり, 金額に対して両替の場合の数を計算する手続きは書けるだろうか.

この問題は再帰的手続きとして単純な解がある. 使える硬貨をある順に並べたとしよう. すると次の関係が成り立つ:

n種類の硬貨を使う, 金額aの両替の場合の数は:
• (a)最初の種類の硬貨以外を使う, 金額aの両替の場合の数, 足す
• (b)dを最初の硬貨の額面金額[denomination]として, n種類の硬貨を使う, 金額a-dの両替の場合の数

つまり1セントと5セントの2種類の硬貨で10セントにするには, 最初の種類の硬貨は5セントであり, 5セント以外の硬貨, つまり1セントで10セントにする場合の数(下の図で赤枠の場合)と, 5セントと1セントで10セントから5セント引いた5セントにする場合の数(青枠の場合)の和である.

また再帰の終わり

• (c)aがちょうど0なら, 両替の場合の数は1
• (d)aが0より少なければ, 両替の場合の数は0
• (e)nが0なら, 両替の場合の数は0
も考えなければならず, 結局プログラムは以下のようになる.

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)                ;(c)
        ((or (< amount 0) (= kinds-of-coins 0)) 0);(d)と(e)
        (else (+ (cc amount             ;(a)の場合
                     (- kinds-of-coins 1))
                 (cc (- amount          ;(b)の場合
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

10セントの両替で, ccの呼ばれ方を図にすると下のようになる. 頂点の(10 2)はamountが10, kinds-of-coinsが2でccが呼ばれるの意. 左下(10 1)への枝は(a)の下請け, 右下(5 2)への枝は(b)の下請けであり, さらに下請けが次々と呼ばれることを示す. さらに右下方向へ延びる枝が, 図には全体で3本見えるが, この最後が(c)の1通りを返してきて, 結局35回呼ばれ, 3通りになる.


このプログラムの, 100セントの両替では, 関数ccは 15499回呼ばれた. その解析がこの表である.


表の横はamount, 縦はkinds-of-coinsで, 横の見出しの「--」はその間の数, つまり0と5の間なら, 1,2,3,4のことである. amountは硬貨3種類のときに-5で3回呼ばれる. これは(cc 5 3)の時で, 5セントから10セントを引こうとして生じる.

この表の数値を全部足すと, 15499になる. また数値の入っている場所は250個所ある. つまり250通りで呼ばれるのである. 赤枠内のamount=0の欄を足すと, 解の292が得られる.

メモ化

これとかFibonacci数の計算のプログラムのような再帰プログラムでは, 同じ引数で関数を何回も呼ぶことによくなる. 上の計算でも引数の異なる呼出しは, 250回である. こういう時には, メモ化という手法が有効である.

小学生の頃, 長い割り算(商の桁数が多い)をするなら, まず除数の2倍, 3倍,..., 9倍の表を作ってから割り算の取り掛かったが, メモ化は表を新しい引数の組で関数を計算するたびに作るのである.

SICPでは, 3.3.3節の最後にメモ化の話題がある. それに倣って, memo-ccを作ってみた.

(define (make-table)  ;和訳SICP 159ページにあるmake-table
  (let ((local-table (list '*table*)))
    (define (lookup key-1 key-2)
      (let ((subtable (assoc key-1 (cdr local-table))))
        (if subtable
            (let ((record (assoc key-2 (cdr subtable))))
              (if record
                  (cdr record)
                  false))
            false)))
    (define (insert! key-1 key-2 value)
      (let ((subtable (assoc key-1 (cdr local-table))))
        (if subtable
            (let ((record (assoc key-2 (cdr subtable))))
              (if record
                  (set-cdr! record value)
                  (set-cdr! subtable
                            (cons (cons key-2 value)
                                  (cdr subtable)))))
            (set-cdr! local-table
                      (cons (list key-1
                                  (cons key-2 value))
                            (cdr local-table)))))
      'ok)
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unknown operation -- TABLE" m))))
    dispatch))

(define (memoize f) ;和訳SICP 160ページのmemoizeを2次元化
  (let ((table (make-table)))
    (define get (table 'lookup-proc))
    (define put (table 'insert-proc!))
    (lambda (x y)
      (let ((previously-computed-result (get x y)))
        (or previously-computed-result
            (let ((result (f x y)))
              (put x y result)
              result))))))


(define memo-cc       ;和訳SICP 22ページのccをメモ化
  (memoize (lambda (a k)
    (set! cccount (+ cccount 1))
    (cond ((= a 0) 1)
          ((or (< a 0) (= k 0)) 0)
          (else (+ (memo-cc a (- k 1))
              (memo-cc (- a (first-denomination k)) k)))))))

これでやってみると, memo-ccが呼ばれたのはちょうど250回であった.