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…