カテゴリ
全体プログラミング scheme verilog 未分類 以前の記事
2016年 04月2016年 03月 2016年 02月 2016年 01月 2015年 12月 2015年 11月 2015年 10月 2015年 09月 2015年 08月 2015年 07月 2015年 06月 2015年 03月 お気に入りブログ
PHPで競技プログラミングメモ帳
最新のトラックバック
ライフログ
検索
タグ
racket
その他のジャンル
ブログパーツ
最新の記事
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
|
12/20の「林先生が驚く初耳学!」で林修さんが披露していた結婚に関する数学的考察について、シミュレーションで検証してみようと思いました。
この考察では、20歳から35歳の間に出会う人間のうち、一番自分とふさわしい相手と結婚するにはどうするのが最適か?という問題について扱っています。 ここでは、結論だけを書かせていただきますが、「20歳から35歳の間に出会う人間をn人とすると、最初に出会う(1/e)n人(つまり0.37n人)とのお付き合いでは結婚しないでおき、それ以降は、今までに付き合った人よりもいい人であれば結婚するのがよい」のだそうです。 さて、シミュレーションでは、集合{0, ..., n-1}の置換(permutation)を生成し、t人見送った時の自分と一番ふさわしい相手と結婚する確率、または自分が結婚するのが何番目の相手であるかということの期待値を算出してみます。 まず、(make-permutation n)関数を記述しました。置換のリストを出力する関数です。 >(make-permutation 3) ((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0)) しかし、この関数はnを多くした時にメモリを大量に消費するので、代わりに次のような関数を用意しました。 #lang racket (require point-free) (define (power-list l1 l2) (if (null? l2) l1 (foldr append empty (map (lambda (x) (map (lambda (y) (append x y)) l2)) l1)))) (define (for-each-permutation proc n) (define (req header rest) (if (null? rest) (proc (reverse header)) (for-each (lambda (n) (req (cons (list-ref rest n) header) (append (take rest n) (drop rest (add1 n))))) (range (length rest))))) (req empty (range n))) しかし、この関数を持ってしても思った以上の計算効率が得られないようです。次のベンチマークを実行してみました。 (define (benchmark n) (time (let ((a 0)) (for-each-permutation (lambda (x) (set! a (add1 a))) n) a))) ベンチマークの実行結果です。 > (benchmark 5) cpu time: 0 real time: 0 gc time: 0 120 > (benchmark 6) cpu time: 0 real time: 0 gc time: 0 720 > (benchmark 7) cpu time: 32 real time: 36 gc time: 32 5040 > (benchmark 8) cpu time: 47 real time: 55 gc time: 31 40320 > (benchmark 9) cpu time: 329 real time: 323 gc time: 62 362880 > (benchmark 10) cpu time: 3141 real time: 3132 gc time: 690 3628800 > (benchmark 11) cpu time: 36218 real time: 36340 gc time: 9431 39916800 n=10で3.1秒、n=11で36.2秒かかっています。置換の個数はn!(nの階乗)で与えられるので、n=12, 13, 14, 15のときはそれぞれ6分、78分、18時間、11日かかるものと考えられます。20歳から35歳の間に15人の相手と付き合う人もなかなかなものだと思いますが、このような場合は少し方法を変えたほうが良さそうです
by tempurature
| 2015-12-22 00:27
| scheme
| ||||||||||||||||||||||
ファン申請 |
||