元記事:組合せ最適化でグループ分け
元々記事:【日常に潜む最適化問題】受験者をなるべく均等に試験会場に割り振るアルゴリズム
が勉強になったので、Haskellでやってみたメモ。
「組合せ最適化でグループ分け」Haskellでやってみたの補足です。
アルゴリズム
アルゴリズムについては、元々記事:【日常に潜む最適化問題】受験者をなるべく均等に試験会場に割り振るアルゴリズムの中で、5グループ、3部屋の例で詳しく説明されています。
元々記事より引用：
Haskellでやってみる際にも、この通り踏襲させていただくことにしました。
ただし、配列でforループでなく、リストで畳み込みでやるので当然違ってくるはず。
「Pythonによる実装」では、どうも組み合わせとかの便利なライブラリを使っているようなのですが、その辺の知識もまったくありません。
何度か試行錯誤して、これだったら畳み込めんじゃね?と思いついた時の手計算のメモです。
やってることは同じですが、元々の部屋の配列とかは脇に置いといて、値の流れだけをグラフ化してみました。
僕にとっては十分絶望的な複雑さですが、しばらく眺めていたら
- リストの先頭値で初期値を作って
- リストの残りで畳み込み
という流れが、部分部分に、やがて全体に見えてきました。
また、
- 部屋の値は、それまでの履歴で確定している値と、現在の部屋でまだ確定していない値と、わけておくと操作が簡単。
- 値と履歴をまとめておくと良さげ。
- 部屋のマトリックスは考えなくてよい。
- 履歴を組み合わせで計算する必要はない。
- あらかじめ、各部屋に有効なグループの数のリスト
[ [6, 5, 4], [5, 4, 7], [4, 7, 5] ]を作っておくと良さげ。
うん、これだったらforループやら配列への再代入やらなくてもできそう...
環境
Haskell for Mac
何か助けてくれそうなのが欲しかったので、有料ですけど使ってみました。
Playgroundで直ぐ試せるし、コードを修正するとPlaygroundに直ぐ反映されるので、何か駄目なことをしたときにすぐ分るというのが便利です。
Haskell for Mac でちょっと Haskell をさわってみる
Atom
AtomでHaskellが使えるようにして、Haskell for Macから外部エディタとして立ち上げています。
型を教えてくれたり、もっと賢そうな書き方を教えてくれます。
関数合成とかさっぱりでしたが、いわれるがまま書き換えているうちに何となく" . "の使いどころがわかってきました。なるほど。" $ "とは違うのね、という今日このごろです。
Qiitaでたくさんのかたがやりかたを教えてくださっています。この辺りを参考にさせていただきました。
ATOMのide-haskell導入手順（MacOS X）
Atom EditorでHaskell