星田さんの記事へのコメント。
しかしパスカルの三角の応用だったとは・・だから組み合わせの途中でいきなり登場してたのか！（悟り） いや、突然変なのぶっこんでくるなぁ・・とは思ったんですよ（Junk scriptsのまとめページには解説などは無くてコードが列挙されているだけなのだ！）。まさかヒントになってたとは・・
うん、多分その辺の知識が欠けてたのが混乱した原因じゃないのかなぁ、と。
んで、もう１つ重要なのは、「組み合わせの数の計算」自体に対して、パスカルの三角形がアンチョコになる、って事なんです。
これを見ればそれこそ例えば
とかすぐ分かる(笑)。一々計算せんでも良い。
数学のテストとかだとアンチョコ使用したらダメで、自ら地道に計算する事を要求されるけど、テストを離れればいくらアンチョコを使っても良い。
と言うか、数学ってそもそも「計算の面倒を避ける為に」証明とかしてんのね(笑)。よってこういうカンジで一旦証明されてる事はバンバン使えばいいんです。むしろそのために数学があるって言って良い。
ちなみに、プログラムを書く、ってのは数学ではない。ただし、一旦証明された数学に付いては「パクって使って」いいんです。こういうのをザックリと「応用数学」(Applied Mathematics)と呼びます。
プログラミングも、他には例えば物理も「応用数学」と言う範疇です。数学者みたいに色々自ら証明せんでも、一旦証明されたモノはガンガン利用していい、っつー気楽な立場ですね(笑)。
上のパスカルの三角形と組み合わせの数、なんつーのを利用する、ってのはまさしく「応用数学」です。
しかし再帰って不思議ですね・・分かった上でコードを見返しても、なんでこんな単純な表記で組み合わせの生成が出来るのか不思議に思ってしまう。
うん、でも関数型言語ユーザーとしては「そういうモンだ」って思っておけば良い、ってのが１つの立場ですよね(笑)。
つまり「抽象性の高い言語を使ってる」ってのは、問題を抽象的に記述さえすれば「あとはプログラミング言語が勝手に頑張ってくれてる」って思って無視しとく、って事でもある(笑)。
逆に、C言語ユーザーみたいにハードウェアを直に叩くような人たちの方が「何でやねん?」とか強く思う傾向があるみたい。その辺が、やっぱり「再帰を黒魔術臭く」感じる原因でもあるんですよ。メモリとスタックを使って、どうやってこういうプログラムを「具体的」にコンパイルして実行するのか物凄く気にする(笑)。彼らは実は「抽象度が高い高級言語の世界には住んでいない」んですよね。具体的にメモリがどう使用されてCPUが直にどういう演算をしてるのか考えちゃう人たちなんで(※1)。
ここでは実際に、自分で筆算で展開してみても良いと思います。言わば人間トレースだな(笑)。
nからk取る組み合わせ
が実際の組み合わせの「集合」を表すとする。
また、集合に含まれる全ての集合にある値を追加する事を、暫定的に
と表現する、とする。
そうすると例えば、5から３つ取る組み合わせは
と表現出来るわけだ。
これを展開していくと。
となって組み合わせが得られる、と(笑)。ベースケースまで展開していって各条件に従って「mapしながら値を集合に足して行く」ってのがポイントで、実際プログラムがやってる事はこれです。
まぁ、もっと小さい条件で検算してみてもいいでしょう。いずれにせよ、ベースケースまで展開、その後作用させて元に戻ってくる、って事ですね。まさしくトレースだ。
(計算するよりLaTeX使う方が大変だった・・・・・・orz)
公式のnとrとコード内を見比べてみるとコード内のnは公式のr、コードのcdrが公式の(n-1)に対応してますよね？
いや、逆かな。nはn。rの方がcdrに対応している。
ひょっとして他の数学的スクリプトでも同じように計算のタイミングに合わせて出力させたりする事が出来るってことなんでしょうかね。
はい、出来ますね。
※1: ここで言うC言語ユーザーはいつも批判してる「C言語脳」とは必ずしも一致しない。むしろアセンブリ言語や機械語レベルでプログラムがどう動くか良く分かってる人たちが主に対象だ。
なお、実の事を言うと、これらC言語のエキスパート達だけじゃなく、ANSI Common Lispのエキスパートも同様の傾向がある。彼らもANSI Common Lispのコンパイラがどういう機械語なりバイナリを吐き出すか、かなり熟知してて、それは当然、アセンブリ言語や機械語レベルでも(やらないけど)プログラミング出来るエキスパートでもある、と言う事だ。
