シャッフルしたいです

レポートが忙しく感じて手がつかないので、プログラムを書いてなかったのでちょっと書いてみる。

すでに古いけども、Radium SoftwareでThe Danger of Naïvetéが紹介されていた。配列の要素をランダムに並び替えたいけど、素朴に書くと偏りが出るんじゃない？　っていう問題らしい。

素朴な方法っていうと、n個の要素から1つを引き抜いて新しい要素の上に順番に載せていくのが楽そうだ。

(defun shuffled-list-sub (n l r)
  (if (= n 0)
	  l
	(progn (setq x (random n))
	  (shuffled-list-sub (1- n) (append l (list (elt r x))) (delete (elt r x) r :count 1 :start x)))))
(defun shuffled-list (&rest r)
  (make-random-state)
  (let (x)
	(shuffled-list-sub (length r) nil r)))

こんな感じだろうか。リストから特定部位を消す方法が良く分からなかったので、その部分は回りくどいけど、イメージ通り。subは中に書いた方が良いかな？
　ともかく、これを60000回ほどテストしてみる。テスト結果のリストを作れば良いんだろうが、メモリを食いそうなので配列でも使ってみる。

(defun testcase ()
  (let ((ar (make-array 6 :initial-element 0)))
  (dotimes (x 600000)
	(let* ((test (shuffled-list 1 2 3))
		   (g (position test '((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) :test 'equal)))
	  (when g (setf (aref ar g) (1+ (aref ar g))))))
  ar))

これでそんなに偏るように思えないけどなあ・・・。

(compile 'testcase)
(testcase)
>> #(99899 99875 99997 100659 99660 99910)

うん、1％も偏らないね！　で、何が問題だったのかな？