# 有什麼不錯的 shuffle 算法嗎？

``````                      a←⎕ ⍝ evaluated input, assign to "a"
⍴a   ⍝ length
⍳⍴a   ⍝ 1 2 .. length
⌽⍳⍴a   ⍝ length .. 2 1
i←       ⍝ assign to "i"
?i        ⍝ random choices: (1..length)(1..length-1)..(1 2)(1)
i{            }¨?i        ⍝ for each index ⍺ and corresponding random choice ⍵
a[⍺⍵]←a[⍵⍺]            ⍝ swap a[⍺] and a[⍵]
←                 ⍝ in Dyalog, assignment returns its right-hand side
⊃                       ⍝ first element, i.e. a[⍵]
⍝ the result from {} is an array of all those a[⍵]
``````

CL21 写起來是这樣的

``````(defun generate-random-array (length)
(let (a)
(setf a #())
(loop for i from 1 to length
do (push i a))
(nreverse (map #'random a))))

(defun shuffle (array)
(let* ((arr array)
(leng (length array))
(rand (generate-random-array leng)))
(loop for i from 0 to (1- leng)
do (rotatef (aref arr i) (aref arr (elt rand i))))
arr))

(shuffle #(1 2 3 4 5 6 7 8 9))
;;=> #(1 7 3 6 9 4 2 5 8)
``````

Elisp 版

``````(defun random-array (length)
(let (a)
(cl-loop for i from 1 to length
do (push i a))
(setq a (vconcat a))
(map 'vector #'random a)))

(defun shuffle (array)
(let* ((leng (length array))
(rand (random-array leng)))
(cl-loop for i from 0 to (1- leng)
do (cl-rotatef (aref array i) (aref array (elt rand i))))
array))

(shuffle [1 2 3 4 5 6 7])
;; => [7 2 1 5 3 6 4]
``````

map is an alias for ‘cl-map’ in ‘cl.el’.

vector 不好 concat 和 trim。大概也沒人会特地在 Emacs 里用 rope。Cons 好歹也算是 binary tree。真要內存吃紧也就不会用 GNU/Emacs 了。

2 个赞

Vector 也很常用，用到的地方也不少，Array 类型（包括 Vector）的一个特点是长度固定，所以你没法添加或删除元素。

``````(defun -shuffle (list)
(declare (pure t) (side-effect-free t))
(let* ((source (copy-sequence list))
(random-nums (->> list
length
(number-sequence 1)
(-map #'random)
nreverse))
result)
(--each random-nums
(setq source (-rotate it source))
(push (car source) result)
(!cdr source))
result))
``````

dash.el投了个稿

1 个赞