月謝3500円のそろばん塾で出たチャレンジ問題
「子供が通っているそろばん塾で、みんなで競う系の問題が出されたのを見ていると、ちょっとムズムズしてしまいVS2008を起動してしまった、の巻き」です・・・大人気ない。
お題
| 商品 |
金額 |
| プロ野球 |
19373円 |
| ディズニーランド |
20453円 |
| 回転ずし |
15906円 |
| ピアニカ |
3351円 |
| 子供部屋リフォーム |
238440円 |
| . |
|
| . |
|
| . |
|
というような商品リストがあり、この中で好きな組み合わせで買い物をして、合計が50万円に一番近い人の勝ち、というものです。
データの用意
とりあえず、こんなリストを作ってデータを与えます。
let goods = [ ("プロ野球", 19373)
("ディズニーランド", 20453)
("回転ずし", 15906)
("ピアニカ", 3351)
("子供部屋リフォーム", 238440)
("デジタルビデオカメラ", 156097)
("お花畑", 29087)
("たこ焼き", 534)
("フーセンガム", 134)
("電動歯ブラシ", 4282)
("CDプレーヤー", 36307)
("マーブルチョコレート", 149)
("弁当箱", 950)
("さけ缶", 568)
("リポD", 1737)
("机いす", 67275)
("サーカス", 11419)
("五月人形", 208730)
("目覚まし時計", 2250)
("ロボット", 109385)
("天体望遠鏡", 40243)
("にくまん", 155)
("手打ちチャーシュー麺", 565)
("イチゴケーキ", 3926)
("お好み焼き", 6238)
("ワンピース", 7301)
("潮干狩り", 19671)
("熱帯魚", 6401)
("シャボン玉", 382)
]
順列発生
まず最初に、商品一覧から任意の個数の商品を選択する組み合わせを全て出力するシーケンスを作ってしまいましょう。
let rec gen l =
seq {
match l with
| [] -> yield []
| h :: t ->
let rest = gen t
for g in rest do
yield (None :: g)
yield (Some h :: g)
}
val gen : 'a list -> seq<'a option list>
こんな関数です。商品リストを取り、買うものをSome 商品名 * 金額で、買わないものをNoneで表したリストのシーケンスを返してくれます。
関数型脳が出来上がるまでは、この関数の実装を見ても「何でこれが順列を発生するのかさっぱりわからない」と思います。僕も半年前まではこういう関数一つ作るのに１日七転八倒していました。この実装についての解説は、一番下に番外編として付け加えておきます。考え方も含めて書いてみますので、こういう関数ができるまでの発想の道筋みたいなものを知りたい人は是非読んでみてください。
念のためにテストデータを与えてテストしてみましょう。
let testdata = [ ("A", 1)
("B", 2)
("C", 3)
]
> Seq.iter (printfn "%A") (gen testdata);;
[null; null; null]
[Some ("A", 1); null; null]
[null; Some ("B", 2); null]
[Some ("A", 1); Some ("B", 2); null]
[null; null; Some ("C", 3)]
[Some ("A", 1); null; Some ("C", 3)]
[null; Some ("B", 2); Some ("C", 3)]
[Some ("A", 1); Some ("B", 2); Some ("C", 3)]
val it : unit = ()
大丈夫そうですね。
計算
let adder =
List.fold (fun i a -> match a with
| None -> i
| Some ((s : string), v) -> i + v) 0
val adder : ((string * int) option list -> int)
これは、genが発生したリストを一つとり、Someの金額部分だけを取り出して合計を出す関数です。
let calcs sets = Seq.map (fun s -> s , adder s) sets
val calcs : seq<(string * int) option list> -> seq<(string * int) option list * int>
そして、それをシーケンス全てに適用した結果を計算結果のシーケンスにして返します。
さっきのテストデータでテストしてみます。
> Seq.iter (printfn "%A") (testdata |> gen |> calcs);;
([null; null; null], 0)
([Some ("A", 1); null; null], 1)
([null; Some ("B", 2); null], 2)
([Some ("A", 1); Some ("B", 2); null], 3)
([null; null; Some ("C", 3)], 3)
([Some ("A", 1); null; Some ("C", 3)], 4)
([null; Some ("B", 2); Some ("C", 3)], 5)
([Some ("A", 1); Some ("B", 2); Some ("C", 3)], 6)
val it : unit = ()
金額の合計が最後に付け加えられています。
結果取得
これらの計算をまとめ上げて、フィルタを追加し、合計が50万円になるものだけを抜き出します。
let ans g =
g |>
gen |>
calcs |>
Seq.filter (fun (l,v) -> v = 500000)
val ans : (string * int) list -> seq<(string * int) option list * int>
最後の関数は、計算結果のリストを若干見やすく表示するだけのプリティプリンタです。
let pp = List.iter (fun v ->
match v with
| None -> ()
| Some (s, v) -> printf "%s : %d円 " s v
)
val pp : ((string * int) option list -> unit)
解答は以下のようなコードで得られます。
Seq.iter (fun (l, total) -> pp l; printfn " -> 計%d円" total) (ans goods)
プロ野球 : 19373円 ピアニカ : 3351円 デジタルビデオカメラ : 156097円 たこ焼き : 534円 フーセンガム : 134円
電動歯ブラシ : 4282円 CDプレーヤー : 36307円 マーブルチョコレート : 149円 弁当箱 : 950円 さけ缶 : 568円
机いす : 67275円 五月人形 : 208730円 目覚まし時計 : 2250円 -> 計500000円
プロ野球 : 19373円 ディズニーランド : 20453円 ピアニカ : 3351円 お花畑 : 29087円 たこ焼き : 534円
CDプレーヤー : 36307円 弁当箱 : 950円 さけ缶 : 568円 リポD : 1737円 机いす : 67275円 五月人形 : 208730円
目覚まし時計 : 2250円 ロボット : 109385円 -> 計500000円
ピアニカ : 3351円 子供部屋リフォーム : 238440円 電動歯ブラシ : 4282円 CDプレーヤー : 36307円
マーブルチョコレート : 149円 さけ缶 : 568円 机いす : 67275円 ロボット : 109385円 天体望遠鏡 : 40243円 -> 計500000円
プロ野球 : 19373円 ピアニカ : 3351円 CDプレーヤー : 36307円 マーブルチョコレート : 149円 弁当箱 : 950円
さけ缶 : 568円 机いす : 67275円 サーカス : 11419円 五月人形 : 208730円 目覚まし時計 : 2250円
ロボット : 109385円 天体望遠鏡 : 40243円 -> 計500000円
ディズニーランド : 20453円 たこ焼き : 534円 CDプレーヤー : 36307円 マーブルチョコレート : 149円
弁当箱 : 950円 さけ缶 : 568円 リポD : 1737円 机いす : 67275円 サーカス : 11419円 五月人形 : 208730円
目覚まし時計 : 2250円 ロボット : 109385円 天体望遠鏡 : 40243円 -> 計500000円
ディズニーランド : 20453円 ピアニカ : 3351円 お花畑 : 29087円 たこ焼き : 534円 電動歯ブラシ : 4282円
マーブルチョコレート : 149円 弁当箱 : 950円 リポD : 1737円 机いす : 67275円 サーカス : 11419円
五月人形 : 208730円 目覚まし時計 : 2250円 ロボット : 109385円 天体望遠鏡 : 40243円 にくまん : 155円 -> 計500000円
.
.
.
計算結果はみつかるごとに表示されるので、止めたいならVisualStudioのF#インタラクティブで実行している場合はCtrl+.で止まります。 fsi.exeの場合はCtrl+zです。
ちょうど50万円になる組み合わせは何件あるのでしょうか。
Seq.length (goods |> gen |> calcs |> Seq.filter (fun (l,v) -> v = 500000));;
val it : int = 1104
>
1000通り以上あるようです。ところが、ちょっと試してもらえるといいのですが、実際に電卓（もしくはそろばん！）を片手に、試行錯誤でこの解のうちどれか一つにでもたどり着くのはほとんど不可能に近い気がします（そろばん塾での課題が「一番50万円に近い人の勝ち」になっているのはそのためです）。順列組み合わせとは恐ろしいものですが、それを割と朴訥にこなしても、2の29乗、だいたい５億通りの計算をちょっとコーヒーを淹れてるぐらいの時間にこなしてしまう今のコンピュータも大したもんだと思います。
まとめ
結局のところ、こういう問題は対象の一覧から計算対象の一覧のシーケンスをどうやって抜き出してくる（ここでは関数gen）かにかかっていて、それができれば後はかなり単純な作業といえます。
関数型言語のいいところは、こういう問題を「一覧を列挙する」作業と「一覧から条件に該当するものだけを抽出する」作業に完全に分けて考え、実装できることに加えて、こういう実装をしたとしても、実行効率やメモリ利用効率がさして落ちないことにあるといえます。
どういうことかと言うと、
let ans g =
g |>
gen |>
calcs |>
Seq.filter (fun (l,v) -> v = 500000)
という関数の絵面だけを見ると
- genが生成した5億個のリストをメモリ上に一時保管して
- その5億個の要素でまたループを回して合計を計算して
- その5億個の要素でまたループを回って50万円のものだけ抜き出す
というような処理を書いているように見えるのですが、実はそうならず、
- genがシーケンスの要素を一つ作成したら
- すぐにcalcsがその合計を計算して
- その結果がすぐにfilterに渡され、合致する場合はyieldし、しない場合はgenに次の要素を要求する
という、ストリーミングっぽい至極真っ当な処理にコンパイラによって展開され、それが実行されているということです。
このマジックはF#のシーケンスとそれを支えるワークフロー（計算式）、果てはその論理的な基盤となるモナドからもたらされているもので、ただ使うだけでもそのメリットを十分享受できますが、その奥で動いているメカニズムについて探ることもまた大変な勉強になります。機会があれば触れてみてください(「
Seqのlazyさ加減に萌」が多少参考になるかもしれません）。
実は「年俸1000万」以来、この手の問題に過剰反応する体になってしまいました。
こういうプログラムをチョコチョコ作ると、「関数型のツボ」みたいなところを忘れないで済みそうなんで、みなさんもネタがあれば手を動かしましょう！
付録：関数genの作り方、考え方
まず、どういう関数を作ろうとしているのかを、冷静に冷静に考えて整理します。その際、入力の型、出力の型、関数に求められる性質（仕様）などを押さえておきます。この過程で使う道具はテキストエディタでもかまいませんし、紙と鉛筆でも構いません。
入出力の型は、
- 入力の型：何かの型の値のリスト（'a list)
- 出力の型：入力された型のオプション型のリストのシーケンス（seq<'a option list>）
求められる性質は、
- 出力シーケンスの数は、２の入力リストの要素数乗になるはず。
- 入力リストの項目の数と、出力シーケンスの要素となるリストの項目の数は変わらない
- よって入力リストが空リストの場合、空リストを一つだけ持つシーケンスが出力シーケンスとなる（[] -> [| [] |]）
- 入力リストの要素が一つの場合は、出力するべきなのは出力が「Noneだけのリスト」と「Some（入力された一つの要素）だけのリスト」の二つになっているようなシーケンス（[A] -> [| [None]; [Some A] |]）
- 入力リストの要素が二つの場合は、出力するべきなのは出力が「[None; None]」と「[Some (二つ目の要素];None」と「[None;Some（最初の要素）]」と「Some (二つ目の要素];Some（最初の要素）]」の四つになっているようなシーケンス（[A;B] -> [| [None;None]; [Some B; None]; [None;Some A]; [Some B; Some A] |]）
ここまではいいでしょうか。割と当たり前のことを書いていると思います。
ここからが正念場です。要素が二つのケースまでスケッチしたら、入力0個の出力から入力1個の状態を作るにはどうするか、を考えます。この場合は、仮に0個の出力[]を使って、入力1個の出力が[| [None] :: []; [Some A] :: [] |]という形で表せることに着目します（これは[| [None]; [Some A] |]と同じです）。入力0個の出力の前にNoneを付け加えたリストと、Some Aを付け加えたリストの二つを入力1個の出力とできないか、と考えるのです。
推測が立ったら、同じルールが個数1の出力から個数2の出力に使えることを確認します。この場合は[| [None]; [Some A]|]のそれぞれの要素の前にNoneを付け加えたリストと、Some Bを付け加えたリストは、[| [None;None]; [Some B; None]; [None;Some A]; [Some B; Some A] |] となりますので、最初に書き出したものと一致しています。このルールで合っているようです。
そうとわかれば、ルールを整理します。
- リストが空なら、空リスト一つのシーケンスを返す。
- リストが空でない場合は、そのリストの二つ目以降の結果を今作ろうとしている関数で取得し、その結果の要素一つ一つに対して、前にNoneを付けたリストと、リストの一つ目の要素を付け加えたリストを作成してシーケンスとする。
このルールなら、要素が増えるごとにシーケンスの要素数が倍になっていくことも納得できます。
プログラムの骨格はこんな風になるはずです。
let rec gen l =
seq {
match l with
| リストが空なら -> yield 空リスト
| h :: t -> // リストがh::t（hが先頭、tは二つ目以降（空リストの場合もあり））で表せる場合
let rest = 二つ目以降のリストをgenに与えてシーケンスを得る
for restのそれぞれの要素に対して do
yield 要素の前にNoneを加えたものをシーケンスの要素とする
yield 要素の前にSome h（先頭の要素）を加えたものをシーケンスの要素とする
}
これをそのまま実装したのが、先に挙げたgen関数です。
let rec gen l =
seq {
match l with
| [] -> yield []
| h :: t ->
let rest = gen t
for g in rest do
yield (None :: g)
yield (Some h :: g)
}
大切なのは、
- 要素が0の場合から考えていくこと
- 要素が1の場合を考えるときに、それを「要素0の場合」を使って表現できないかを考えること
- 要素が2の場合を考えるときに、要素が1の場合を考えるときに使った表現方法が成立することを確認する。そうなっていない場合は、そうなるような規則を探す。
ということです。１個→2個のルールのほうが考え易そうならそっちから攻めてもかまいません。
最後に一つ注意があります。ここで書いた関数genと同じものを作る方法はいくらでもあります。ここで挙げた方法が一番いい、と主張する気も毛頭ありません。考え方の一例として読んでください。
（文責：片山 功士 2012/05/12）
今日： - 人
昨日： - 人
トータル： - 人
最終更新：2012年05月20日 14:12
