* DONE Randomize a list in Emacs
CLOSED: [2014-09-06 Sat 10:08]
:PROPERTIES:
:categories: emacs_lisp
:date: 2014/09/06 10:08:04
:updated: 2014/09/06 15:11:50
:END:
I have an application where I have a list of userids, and I want to randomize the order of the list. Today, I explore some ways to do that. The first idea is to simply mimic the algorithm in Python's random.shuffle algorithm.
#+BEGIN_SRC python
def shuffle(self, x, random=None):
"""x, random=random.random -> shuffle list x in place; return None.
Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.
"""
if random is None:
random = self.random
_int = int
for i in reversed(xrange(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = _int(random() * (i+1))
x[i], x[j] = x[j], x[i]
#+END_SRC
It looks like we loop through the elements, and swap them at random.
We have a similar feature for xrange in emacs-lisp:
#+BEGIN_SRC emacs-lisp
(number-sequence 1 5)
#+END_SRC
#+RESULTS:
| 1 | 2 | 3 | 4 | 5 |
Note that number-sequence includes the last value, unlike xrange. And for reverse:
#+BEGIN_SRC emacs-lisp
(reverse (number-sequence 1 5))
#+END_SRC
#+RESULTS:
| 5 | 4 | 3 | 2 | 1 |
Of course, we can select random numbers:
#+BEGIN_SRC emacs-lisp
(random 5) ; random between 0 and 5
#+END_SRC
#+RESULTS:
: 4
Last, we need to work out how to swap to elements. It looks like this will swap elements 2 and 3. We store element 3 temporarily, set 3 to 2, and then set 2 to the temporarily stored value of 3.
#+BEGIN_SRC emacs-lisp
(let* ((L '(1 2 3 4))
(tmp (nth 3 L)))
(setf (nth 3 L) (nth 2 L))
(setf (nth 2 L) tmp)
L)
#+END_SRC
#+RESULTS:
| 1 | 2 | 4 | 3 |
So, now we can shuffle our list.
#+BEGIN_SRC emacs-lisp
(setq userids '(user1 user2 user3 user4 user5 user6))
(defun swap (LIST el1 el2)
"in LIST swap indices EL1 and EL2 in place"
(let ((tmp (nth el1 LIST)))
(setf (nth el1 LIST) (nth el2 LIST))
(setf (nth el2 LIST) tmp)))
;; now run the loop
(loop for i in (reverse (number-sequence 1 (1- (length userids))))
do (let ((j (random (+ i 1))))
(swap userids i j)))
userids
#+END_SRC
#+RESULTS:
| user4 | user6 | user3 | user2 | user1 | user5 |
The order has certainly changed. It is a little difficult to tell how randomized it actually is, but what is important for my application is that the order is different each time I use it. It looks like this will accomplish that objective. I think this basically implements the algorithm in the Python random.shuffle code. That code does something a little differently. It generates a random float between 0-1, multiplies it by i + 1, and converts the result to an integer. We directly get an integer in the range of 0 to i + 1. I think the result is practically the same.
Finally, let us wrap the whole thing up in a nice neat function for future use. We will use elt instead of nth so it works for arrays too.
#+BEGIN_SRC emacs-lisp
(defun swap (LIST el1 el2)
"in LIST swap indices EL1 and EL2 in place"
(let ((tmp (elt LIST el1)))
(setf (elt LIST el1) (elt LIST el2))
(setf (elt LIST el2) tmp)))
(defun shuffle (LIST)
"Shuffle the elements in LIST.
shuffling is done in place."
(loop for i in (reverse (number-sequence 1 (1- (length LIST))))
do (let ((j (random (+ i 1))))
(swap LIST i j)))
LIST)
#+END_SRC
#+RESULTS:
: shuffle
Example usage for a list:
#+BEGIN_SRC emacs-lisp
(shuffle '(user1 user2 user3 user4 user5 user6))
#+END_SRC
#+RESULTS:
| user4 | user2 | user3 | user5 | user6 | user1 |
And for a vector:
#+BEGIN_SRC emacs-lisp
(shuffle [user1 user2 user3 user4 user5 user6])
#+END_SRC
#+RESULTS:
: [user3 user2 user6 user4 user5 user1]
** Addendum
Artur at http://endlessparentheses.com suggested one can use psetf to swap values. Thanks for the tip, I was not aware of that cool function. It evaluates the values first, then sets them, so there is no need for a temporary storage of a value! Here is an example usage. We could rewrite our swap function like this if we wanted.
#+BEGIN_SRC emacs-lisp
(let ((LIST '(1 2 3 4 5)))
(psetf (elt LIST 2) (elt LIST 1)
(elt LIST 1) (elt LIST 2))
LIST)
#+END_SRC
#+RESULTS:
| 1 | 3 | 2 | 4 | 5 |