12章「サンプリング問題」 - 珠玉のプログラミング(Programming Pearls)
珠玉のプログラミングの12章。
12.5.1
or で必要な分だけつなげる。
12.5.2
各要素を m/n で選び、i = 0 から始める。部分セットの要素数が m になったら完了。
先頭に近い部分セットが選択されやすくなる。
12.5.3
n=6 m=2 で考える。
1回目は必ずセットにない。
2回目は 4/5 でセットにない。(ここでそろう確率は 4/5)
とやっていくと 2 より小さい気がするが証明は難しいな。
12.5.4
難しかったので答え見た。
12.5.5
略。
12.5.6
略。
12.5.7
accumulate して最後に出力。
12.5.8
コード参照。
12.5.9
答え見た。これでうまくいく理由がよく分からなかった。
12.5.10
最後に見た物を記録しておく。それとは別にランダムな index を生成する。
答え見たら全然違った。これは感動した。
12.scm
;; Programming Pearls Chapter 12 (import (rnrs) (mosh) (mosh control) (srfi :27) (srfi :8) (only (srfi :1) list-tabulate) (mosh test)) (define (rand-select n m) (let loop ([select m] [remaining n] [i 0] [results '()]) (cond [(= i n) results] [else (let1 selected? (< (mod (random-integer 10000000000) remaining) select) (display select) (loop (if selected? (- select 1) select) (- remaining 1) (+ i 1) (if selected? (cons i results) results)))])))
珠玉のプログラミング—本質を見抜いたアルゴリズムとデータ構造
posted with amazlet at 09.07.11
ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 5607
ピアソンエデュケーション
売り上げランキング: 5607