有什麼不錯的 shuffle 算法嗎？

Programming
1

最近又開始用 CL 重写麻將遊戲了⋯⋯

想搞个洗牌算法。

目前用的是从 Code Golf 抄的 i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕

                      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]
2

用elisp写呗，我们还可以沾沾光

3

用 CL 写完也能 port 到 Emacs 上的。

4

这个map的subroutine我的Emacs怎么没有？

顺带歪楼问一下，vector的空间占用比list小，但是为什么Elisp里面大家都不用vector?

5

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

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

2 个赞
6

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

7

洗数组元素的话，当然是算法导论刚开始讲随机的那一章中提到的算法啊。

记得场景好像讲的是面试还是什么，在那一章后面部分。

8 
(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 个赞