Randomize a list in Emacs

Posted September 06, 2014 at 10:08 AM | categories: emacs_lisp | tags:

Updated September 06, 2014 at 03:11 PM

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. 

    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]

It looks like we loop through the elements, and swap them at random.

We have a similar feature for xrange in emacs-lisp: 

(number-sequence 1 5)
1 2 3 4 5

Note that number-sequence includes the last value, unlike xrange. And for reverse: 

(reverse (number-sequence 1 5))
5 4 3 2 1

Of course, we can select random numbers: 

(random 5) ; random between 0 and 5

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. 

(let* ((L '(1 2 3 4))
       (tmp (nth 3 L)))
  (setf (nth 3 L) (nth 2 L))
  (setf (nth 2 L) tmp)
L)
1 2 4 3

So, now we can shuffle our list. 

(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
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. 

(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)

shuffle

Example usage for a list: 

(shuffle '(user1 user2 user3 user4 user5 user6))
user4 user2 user3 user5 user6 user1

And for a vector: 

(shuffle [user1 user2 user3 user4 user5 user6])

[user3 user2 user6 user4 user5 user1]

1 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. 

(let ((LIST '(1 2 3 4 5)))
  (psetf (elt LIST 2) (elt LIST 1)
         (elt LIST 1) (elt LIST 2))
LIST)
1 3 2 4 5

Copyright (C) 2014 by John Kitchin. See the License for information about copying.

org-mode source

Org-mode version = 8.2.7c

Discuss on Twitter