How to randomize the order of elements in an alist?

Question

I'm using ielm inside Emacs to randomize an associative list. I'm getting duplicate entries a lot of the time, not sure what I'm doing wrong?

(defun q ()
  "Q."
  (let ((alist))
    (setf alist (q-randomize (q-create-alist)))
    alist))

(defun q-create-alist ()
  "Create alist."
  (let ((alist nil)
        (x 0))
    ;; create alist ((0 . (0 . 0)) (1 . (1 . 1)) (2 . (2 . 2)) ...)
    (dotimes (k 1)
      (dotimes (v 5)
        (push `(,x . (,v . ,k)) alist)
        (setf x (1+ x))))
    alist))

(defun q-randomize (alist)
  "ALIST randomize."
  (dotimes (x (length alist))
    (setf alist (q-swap alist)))
  alist)

(defun q-swap (alist)
  "ALIST swap."
  (let ((rand nil) (item nil) (swapped nil))
    (setf rand (random (length alist)))
    
    ;; ignore the first
    (if (not (eq 0 rand))
        (setf item (assq rand alist)))
    
    ;; don't add nil item
    (if item
        (progn
          (setf swapped (delq (assq rand alist) alist))
          (setf swapped (cons item alist)))
      (setf swapped alist))
    swapped))

ELISP> (q)
((3 3 . 0)
 (1 1 . 0)
 (2 2 . 0)
 (4 4 . 0)
 (4 4 . 0)
 (0 0 . 0))

ELISP> (q)
((1 1 . 0)
 (1 1 . 0)
 (2 2 . 0)
 (3 3 . 0)
 (3 3 . 0)
 (4 4 . 0)
 (0 0 . 0))

Answer 1

This is your problem:

(setf swapped (delq (assq rand alist) alist))
(setf swapped (cons item alist)))

If, for example, rand is 2 then:

swapped is set to something like this: (2 2 . 0) (4 4 . 0) (3 3 . 0) (1 1 . 0) (0 0 . 0)).

And then the first of those sexps sets swapped to (4 4 . 0) (3 3 . 0) (1 1 . 0) (0 0 . 0)), which is fine.

But then you cons item (2 2 . 0) onto alist, which still has element (2 2 . 0).

Your code should first update alist itself to the result of delq:

(setf swapped (setq alist (delq (assq rand alist) alist)))

Answer 2

Here's a much simpler and also more generally reusable FP-style approach:

(require 'dash) ; for `-let' and `-flip'

(defun either (&rest functions) (nth (random 2) functions))

(defun randomize-alist (alist)
  (when alist
    (-let (((head . tail) (funcall (either #'identity #'reverse) alist)))
      (funcall (either #'append (-flip #'append))
               (list head)
               (randomize-alist tail)))))