The previous post of SKILL for the Skilled presented some ways to systematically visit all permutations of a list. As noted, the time to iterate through all permutations of a large list is prohibitive. If the goal is to find a permutation that meets some criteria then it may work perfectly well to simply test the criteria on randomly chosen permutations of the list and continue doing so until some time-out is reached. Choosing a permutation at random is also called shuffling. In this article, I want to look at some ways to shuffle a list. In doing so, we'll also see how random numbers work in SKILL and a few examples of how to use them.
Very easy but not very random
An advantage of the implementation of shuffle_a
below is that it very easy to remember and easy to implement. An important disadvantage is that it does a poor job of shuffling the given list. It basically asks the SKILL built-in sort
to do the work and provides a compare function for sort
to use, which provides some randomness. The SKILL expression (random 2)
returns either 0 or 1 selected at random. Consequently the expression (onep (random 2))
returns either t
or nil
chosen at random. (defun shuffle_a (data)
(sort (copy data)
(lambda (_a _b)
(onep (random 2)))))
For example, (shuffle_a '(1 2))
returns either (1 2)
or (2 1)
, each with 50% likelihood. However (shuffle_a '(1 2 3))
returns one of the following two permutations half of the time (3 1 2)
, (3 2 1)
, and one of the other four permutations the other half of the time. Thus, not all permutations are equally likely. Similarly, there are 24 permutations of (1 2 3 4)
, but (shuffle_a '(1 2 3 4))
returns one of the following eight permutations half of the time: (1 2 3 4)
, (1 2 4 3)
, (2 1 3 4)
, (2 1 4 3)
, (3 4 1 2)
, (3 4 2 1)
, (4 3 1 2)
, or (4 3 2 1)
. And it returns one of the other 16 permutations the other half of the time.
If you need a quick and dirty shuffle algorithm, shuffle_a
is decent and easy to remember. But if you need a good shuffle algorithm, use a different one.
Shuffle by partitioning
The following recursive algorithm can be used to shuffle a list of elements. It works similar to a quick sort, but rather than collecting the large and small elements into two respective lists recursively, it randomly partitions some elements into one sub-list and others into another sub-list, then proceeds to apply the same algorithm recursively onto those two sub-lists. (defun shuffle_b (data)
(cond
((cddr data) ; more than 2 elements?
(let (left right)
(foreach item data
(if (zerop (random 2))
(push item left)
(push item right)))
(nconc (shuffle_b left)
(shuffle_b right))))
((zerop (random 2))
(reverse data))
(t
(copy data))))
Shuffle by random selection
The following algorithm shuffle_c
, works by continuing to randomly choose element at random from the list, push that element onto a new list, and remove it from the old list, continuing until a single element remains, then finally pushing it onto the list. The expression r = (random n)
returns a number 0 <= r < n
(defun shuffle_c (data)
(let ((n (length data))
r
p
shuffled)
(while (cdr data)
;; choose a random element: data[r]
r = (random n) ; randomly choose 0 <= r < n
p = (nthcdr r data)
;; add data[r] to shuffled
(push (car p)
shuffled)
;; remove data[r] from data
data = (nconc (ldiff data p)
(cdr p))
;; decrement n
n--)
(when data
(push (car data) shuffled))
shuffled))
How do you remove an element from a list?
There is a subtle trick in the code for shuffle_c
: how to remove an element from a list. The built-in SKILL function remove
won't exactly do the trick. Actually, remove
works fine if the elements of the list are unique, but not if the list has duplicate elements. The SKILL remove
function actually removes all elements from the given list which are equal to the given element. For example (remove 42 '(0 42 1 42 2 42 3))
will return (1 2 3)
, whereas we want a function, remove_once
which works as: (remove_once 42 '(0 42 1 42 2 42 3)) ==> (0 1 42 2 42 3)
. You might implement remove_once
as follows:
(defun remove_once (data item)
(let ((p (member item data)))
(nconc (ldiff data p)
(cdr p))))
What the shuffle_c
function does is chooses an element of the list by position, and then removes the element in that position. For example, given the list mylist=(42 1 42 2 42 3)
, if we choose the element in position 2 (0-based index), which is the second 42 in the list, we can divide the list in two halves, right and left. The right portion is obtained by calling (nthcdr 2 mylist) ==> (42 2 42 3)
. The left portion is obtained by left=(ldiff mylist right)
==>(42 1). Given right
and left
, we can produce a new list equal to the original list but with the element at position 2 removed by appending the two lists left
and (cdr right)
. How do you select an element at random?
Given a list of elements, the following function will select an element at random from it. (defun random_element (data)
(when data
(nth (random (length data)) data)))
Be careful with this function: if given an empty list, (random 0)
triggers an error. Shorter version of shuffle
The following implementation of shuffle_d
is more or less the same algorithm as shuffle_c
but uses the helper functions random_element
and remove_once
. (defun shuffle_d (data)
(let (shuffled
e)
(while data
e = (random_element data)
(push e shuffled)
data = (remove_once data e))
shuffled))
Challenge to the reader
If you know another clever way to shuffle a list, please post the code to the comment section of this article below. Summary
In this article four versions of the shuffle function were presented. shuffle_a
: a very short implementation of an inferior sorting algorithm shuffle_b
: a recursive divide and conquer shuffle algorithm shuffle_c
: an imperative, iterative algorithm for shuffling shuffle_d
: similar to shuffle_c
but easier because it makes use of helper functions
In addition we looked at two other functions:
remove_once
: an efficient algorithm for removing a maximum of one element from a list random_element
: return a randomly selected element from a list