http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20051024#p04 の正しさについてしばし考えた。リストの各要素について[0,1]区間の一様乱数を振って、その値でsortしていると理解してみた。もっと単純な解釈はないだろうか。 追記 これを実装し…

先日のアルゴリズムは逆向きにしたほうがわかりやすいと思う。Haskellで(効率を無視して)書くと、こういうこと。Arrayを使用する場合はselectOneに代えてswapにしたりすればO(N)にできる。 module Shuffle where import System.Random listShuffle :: StdGen…

前のページ・次のページ。 Web を徘徊していて気になった「次のページ」という記述。これは「後のページ」の方がわかりやすいんではないか。時間を一方向にしか進めない人にとっては 次 = 未来 なのかもしれないけど。http://www.lab2.kuis.kyoto-u.ac.jp/~h…

http://d.hatena.ne.jp/yts/20051022#p1 で言及されたアルゴリズムを実装してみる。 {-# OPTIONS -fglasgow-exts #-} module Shuffle where import Control.Monad.Fix (fix) import System.Random import Control.Monad.ST import Data.Array.MArray import …

http://www.hyuki.com/d/200510.html#i20051020