This came up in another topic recently, and I thought that it could be of interest to others.
Nyquist includes a function for sorting lists (http://www.audacity-forum.de/download/edgar/nyquist/nyquist-doc/xlisp/xlisp-ref/xlisp-ref-242.htm)
For example, to sort a list of numbers in ascending order:
(setf data (list 5 1 9 2 0 4 3 8 6 7))
(format nil "~a" (sort data '<))
;; returns (0 1 2 3 4 5 6 7 8 9)
Caution:
“SORT” is a destructive list function. The function destroys the list data.
For example, if you run as Debug:
(setf data (list 5 1 9 2 0 4 3 8 6 7))
(format t "Sorted data: ~a~%" (sort data '<))
(format t "data = ~a" data)
the debug output is:
Sorted data: (0 1 2 3 4 5 6 7 8 9)
data = (5 6 7 8 9)
Part of the list has been destroyed!
If we wish to keep the list intact, we must recreate it from the returned value. For example:
(setf data (list 5 1 9 2 0 4 3 8 6 7))
(format t "Sorted data: ~a~%" (setf data (sort data '<)))
(format t "data = ~a" data)
the debug output is:
Sorted data: (0 1 2 3 4 5 6 7 8 9)
data = (0 1 2 3 4 5 6 7 8 9)
======================
Swapping values:
Here’s a neat little macro for swapping (exchanging) the values of two variables.
(defmacro swap (x y)
`(let ((temp ,x))
(setf ,x ,y)
(setf ,y temp)))
It’s quite versatile as it can not only be used for variables, but for elements of a list, or elements of an array.
Example: swapping values of a variables:
(defmacro swap (x y)
`(let ((temp ,x))
(setf ,x ,y)
(setf ,y temp)))
(setq a "swans a swimming") ; a string value
(setq b 15) ; an integer value
(swap a b)
(format nil "~a ~a" (/ a 2) b)
;; prints: 7 swans a swimming
Example: Swap left and right channels of the selected track:
;version 4
(defmacro swap (x y)
`(let ((temp ,x))
(setf ,x ,y)
(setf ,y temp)))
(swap (aref *track* 0)(aref *track* 1))
*track*
======================
Back to the original issue:
Randomizing the order of elements in a list
In other words, shuffling the elements of a list to produce a random permutation.
A well known algorithm for this is the “Fisher–Yates shuffle”
This implementation is based on the “modern algorithm” and uses the “swap” macro (above) for exchanging the elements:
;; Fisher-Yates_shuffle (modern algorithm)
;; From: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
;;
;; -- To shuffle an array a of n elements (indices 0..n-1):
;; for i from n-1 downto 1 do
;; j <- random integer such that 0 <= j <= i
;; exchange a[j] and a[i]
; Input is a list
(setf data-list (list 0 1 2 3 4 5 6 7 8 9))
(defun shuffle (data)
"Shuffle a list for a random permutation."
(let ((n (length data)))
(do* ((i (1- n) (1- i))
(j (random (1+ i))(random (1+ i))))
((= i 1) data-list)
(swap (nth i data) (nth j data)))))
(defmacro swap (x y)
`(let ((temp ,x))
(setf ,x ,y)
(setf ,y temp)))
; Test it
(let ((input (format nil "~a" data-list))) ;keep a copy so we can print it
(format nil "Input:\t ~a~%Output:\t ~a"
input
(shuffle data-list)))