Lisp で乱数リストを作る

ちょっとアルゴリズムの基礎をやり直そうと思う。sort と search の有名どころをしっかりと。。。それぞれの特徴やら、有効に使えないケースやらをちゃんと理解しておきたい。
で、とりあえずsortからやろうと思うわけでありますが、sortと言えばランダムなリストが必ずセットになる。そこで、乱数のリストを作るところからやってみようと言うわけであります。何も考えずに要素10の乱数リストを作るとすると以下のようになるだろう。

? (let (tmp)
    (dotimes (i 9)
      (push (random 100) tmp))
    (reverse tmp))
(17 56 75 22 50 76 20 49 29)
? 

今回は特に問題なかった。避けたいと思うのは、random が同じ値を返した場合だ。同じ値だったら、それは使用せずにもう一度作る、としたら以下のようになるが、

? (let (tmp)
    (do ((i 0 (+ i 1)))
        ((eql 10 (length tmp)))
      (let ((v (random 100)))
        (unless (member v tmp)
          (push v tmp))))
    (reverse tmp))
(16 4 61 33 71 87 65 56 92 90)
? 

問題は、何度 (member v tmp) が真を返すかが完全にランダムということ。random の引数を大きくすれば、確率的に同じ値が出る確率は下るが、(random 10)で要素数10で重複のないリストを作る、とかなったら時間がかかるかもしれない。
これは避けたい。要素数に係わらず、要素数以外の要因がコストに関与してくる、という実装はやめたい。そのために以下のようにする。

(let ((init-list (let (tmp)
		   (dotimes (i 999)
		     (push (+ i 1) tmp))
		   (reverse tmp))))
  (let (random-list)
    (do ((x (random (length init-list))
	    (random (length init-list))))
	((eql 10 (length random-list)))
      (push (nth x init-list) random-list)
      (setf init-list (remove x init-list)))
    random-list))

最初に普通のリストを作成し、そこから必要な回数だけ値を取り出す。取り出すたびに最初のリストも小さくなるから、同じ値を二度取ってしまうことはない。最初に要素を作成するというコストがどうしても発生してしまうがこうしておけば、最終的に欲しい要素数のみに依存するように処理を行える。やり直しは発生しない。これを再帰でやるようにすると、以下のようになる。

(labels ((get-any-element (result org-list)
			  (if (eql 10 (length result))
			      result
			    (let ((x (nth (random (length org-list)) org-list)))
			      (get-any-element (append result (list x))
					       (remove x org-list))))))
  (get-any-element nil (loop for i from 1 to 999 collect i)))

これは要素数10の乱数リストが欲しい、という意味だが、要素数を意味する10がget-any-elementの中でハードコーディングされているので、この10を引数で渡すようにしたい。実際には、get-randam-list という感じで定義することになるだろうから、最終的に以下のようにする。

(defun get-random-list (element-count)
  (labels ((get-any-element (result org-list)
			    (if (eql element-count (length result))
				result
			      (let ((x (nth (random (length org-list)) org-list)))
				(get-any-element (append result (list x))
						 (remove x org-list))))))
    (get-any-element nil (loop for i from 1 to (* element-count 10) collect i))))

これを実行してみたときの様子。

? (defun get-random-list (element-count)
  (labels ((get-any-element (result org-list)
			    (if (eql element-count (length result))
				result
			      (let ((x (nth (random (length org-list)) org-list)))
				(get-any-element (append result (list x))
						 (remove x org-list))))))
    (get-any-element nil (loop for i from 1 to (* element-count 10) collect i))))
GET-RANDOM-LIST
? (get-random-list 10)
(3 74 77 25 94 63 23 31 71 18)
? (get-random-list 10)
(43 82 30 54 35 63 88 57 60 36)
? (get-random-list 10)
(100 98 62 18 58 31 10 32 53 68)
? 

毎回異なるリストを取得できている。