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)))])))

珠玉のプログラミング—本質を見抜いたアルゴリズムとデータ構造
ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 5607