In this posting I want to look at several ways of generating
permutations of a list. The problem comes up occasionally in fault
analysis as well as a few other applications.
Don't generate the list
It is usually a bad idea to try to generate a list of all permutations
as the length of that list can be very large for some lists. E.g., a
list of the permutations of a list of length ten will be 10! =
3,628,800. What is generally a better idea is to iterate over the
permutations one at a time without ever generating them all into a
list. This is sometimes referred to as Visiting the
permutations with a visitor function.
Even without accumulating a list of permutations, assuming 1
microsecond per iteration, iterating over the permutations of a list
of 24 elements will take longer than the age of the universe. This is
assuming the universe is 15 billion years old, which is between 23!
and 24! microseconds old. Please someone correct me in the comments
below if my off the cuff calculation is wrong.
In this blog we present ways to implement the
function map_permutations
which can be called as
follows: (map_permutations VISITOR DATA)
,
where VISITOR
is a unary function which will be called on
each permutation, and DATA
is a list of items.
Brute force approach
The following implementation of map_permutations_BF
is
more or less a recursive function which implements N
consecutive foreach
loops, where N is the length of the
given list. Each step, 0<=k<=N, of the recursion makes Nk calls to, the
local function next
. Thus, next
reaches the
k=N level N! times which it has each time accumulated one permutation.
(defun map_permutations_BF (visit data "ul")
(let ((N (length data)))
(labels ((next (so_far k)
(cond
((eqv k N)
(visit (mapcar car so_far)))
(t
k++
(foreach map items data
(unless (memq items so_far)
(next (cons items so_far) k)))))))
(next nil 0))))
The example above is SKILL++ code so as always with SKILL++, you need
to save it in a file with a .ils
extension, or wrap it
in (inScheme ...)
if pasting into the CIW window.
Example: printing the permutations
Here is a few of examples of how to
use map_permutations_BF
. The first example prints each
permutation of (1 2 3 4)
to standard output.
(map_permutations_BF println
'(1 2 3 4 5))
Here is the standard out of evaluating that expression:
(4 3 2 1)
(3 4 2 1)
(4 2 3 1)
(2 4 3 1)
(3 2 4 1)
(2 3 4 1)
(4 3 1 2)
(3 4 1 2)
(4 1 3 2)
(1 4 3 2)
(3 1 4 2)
(1 3 4 2)
(4 2 1 3)
(2 4 1 3)
(4 1 2 3)
(1 4 2 3)
(2 1 4 3)
(1 2 4 3)
(3 2 1 4)
(2 3 1 4)
(3 1 2 4)
(1 3 2 4)
(2 1 3 4)
(1 2 3 4)
Counting the permutations
The second example counts the number of permutations of (1 2 3 4 5 6 7 8 9)
:
(let ((c 0))
(map_permutations_BF (lambda (_) c++)
'(1 2 3 4 5 6 7 8 9))
c)
==> 362880
Collecting a list of permutations
The third example collects and returns the list of permutations of (1 2 3)
:
(let (data)
(map_permutations_BF (lambda (p) (push p data))
'(1 2 3))
data)
==> ((1 2 3) (2 1 3) (1 3 2) (3 1 2) (2 3 1) (3 2 1))
Trying different algorithms
A very good reference source for discussions and implementations of
algorithms in general is
Donald Knuth's
book
Art
of Computer Programming. In particular Volume 4 Fascicle 2
discusses how to generate permutations. The following are three
different algorithms implemented from that fascicle.
PLEASE NOTE that I have not tried to improve the
readability of the algorithms, but rather I've tried to keep the SKILL
code as close as possible to Knuths pseudocode from the book. I
would advise against trying to improve the code. One great
advantage of keeping the code as it is, is that you know it works.
Another argument for keeping it as it is, and resist improving
is that if someone later comes along and reads your code, they can
read the referenced pages of Art of Computer Programming to
discover the justifications for the implementation as well as
discussion of limitations and performance.
Quick review of SKILL prog/go
As with most of the algorithms in Art of Computer Programming,
these algorithms are highly optimized and depend on GOTO.
The GOTO operator in SKILL is called go
and is
only available inside (prog ...)
within traditional
SKILL. Unfortunately, prog
/go
is NOT
available in SKILL++. This means unless you want to convert all
the GOTOs in Knuth's code to some other style, you'll have to
use .il
as your file name suffix when implementing these
functions, or of course you may wrap the code in (inSkill
...)
.
A moral of this story is that sometimes SKILL++ is good for solving
a problem, and sometimes traditional SKILL is better. In the SKILL
language you have both together. You can use the dialect which works
best for your problem space, or you can mix and match as necessary as
your application demands.
The SKILL prog
allows its body to
call return
with an argument which causes
the prog
for to exit and to return the argument which was
given to return
. For example:
(prog ()
(return 42)
(println 'hello))
==> 42
In the previous example, the (prog ...)
form returns 42,
and the line (println 'hello)
is never reached. If while
executing the body of the (prog ...)
form,
no (return ...)
is encountered, the (prog
...)
form returns nil
.
Another Knuthfriendly feature of SKILL prog
but
not the SKILL++ prog
is that it allows toplevel labels
which are valid unquoted operands for the go
operator.
In the following
example, L0
, L1
, L2
,
and L3
are labels. Some of these are used by (go
..)
; in particular (go L1)
, (go L2)
,
and (go L0)
.
(prog (n)
(go L1)
L0
(printf "finished\n")
(return 'done)
L1
n = 0
L2
(printf "n=")
(println n)
L3
(if (n < 12)
then n++
(go L2)
else (go L0))
(printf 'never_reached))
You'll find this prog/go
construct useful when
transcribing Knuth's algorithms.
Plain changes
The following implements algorithm P (Plain changes) from Donald E. Knuth,
The Art of Computer Programming Volume 4 Fascicle 2, Generating All
Tuples and Permutations, page 42.
(defun map_permutations_P (visit data "ul")
(letseq ((n (length data))
(a (listToVector (cons nil data)))
(c (makeVector (add1 n)))
(o (makeVector (add1 n)))
j
s
q)
(prog ()
P1 ; Initialize
(for j 1 n
c[j] = 0
o[j] = 1)
P2 ; Visit
(funcall visit (cdr (vectorToList a)))
P3 ; Prepare for change.
j = n
s = 0
P4 ; Ready to change?
q = c[j] + o[j]
(cond
((q < 0)
(go P7))
((q == j)
(go P6)))
P5 ; Change
(let ((u jc[j]+s)
(v jq+s))
;; swap a[v] with a[u]
a[v] = (prog1 a[u]
a[u] = a[v]))
c[j] = q
(go P2)
P6 ; Increase s
(if (j == 1)
(return)
(s++))
P7 ; Switch direction
o[j] = o[j]
j
(go P4))))
Converting Knuth algorithms to SKILL
 List vs Array
 In SKILL you normally work with lists, and consequently you might
want to visit the permutations of a list. The Knuth algorithms in
this article visits the permutation of a fixed size array. Because of
this, these implementations of
map_permutations
expect
lists as input and output, while internally use arrays inkeeping with
the Knuth algorithm. Converting between list and array is done
using listToVector
and vectorToList
.
 Zero indexed vs. one indexed
 SKILL only provided zerobased arrays. Some of the Knuth
algorithms use onebased and some used zerobased arrays. Where
appropriate, filler elements are used for the 0th element when
the Knuth array is onebased. You'll see expressions such
as
(funcall visit (cdr (vectorToList a)))
in the SKILL
implementations, which means the corresponding array is onebased in
the Knuth algorithm, so we have to discard the 0th element when
passing the data to the visit
function. The following
table summarizes how to
use makeVector
, vectorToList
,
and listToVector
with zeroindexed and oneindexed
arrays.
 allocate  array to list  list to array


N element zeroindexed  (makeVector N)  (vectorToList myarr)  (listToVector mylist)

N element oneindexed  (makeVector N+1)  (cdr (vectorToList myarr))  (listToVector (cons nil mylist))

 Use of
prog
/go
/return
 As described above the use of labels and
GOTO
in the
Knuth algorithms is easily implemented using the SKILL (prog
...)
construct.
 Use of
do
/until
 Some Knuth algorithms use
do
/until
,
which is available in SKILL++ but not in SKILL. We solve this problem
by using the following do_until
macro, which takes a test
expression as first argument, and a body of expressions. The effect
is that the body of expressions is evaluated once, and thereafter it
is evaluated again and again as long as reevaluating the tests
returns nil
.
(defmacro do_until (test @rest body)
`(progn ,@body
(while (not ,test)
,@body)))
 Swapping elements
 Swapping two elements, A and B, can be done as followings, but
when this is done an appropriate comment is added.
A = (prog1 B
B = A)
Ehrlich swaps
The following implements algorithm E (Ehrlich swaps) from Donald E. Knuth,
The Art of Computer Programming Volume 4 Fascicle 2, Generating
All Tuples and Permutations, page 57. According to Gideon Ehrlich, the
original author of this algorithm, the most amazing thing about it is
that it works.
(defun map_permutations_E (visit data "ul")
(letseq ((a (listToVector data))
(n (length data))
(b (makeVector n))
(c (makeVector n+1))
k
j)
(prog ()
E1 ; Initialize
(for j 0 n1
b[j] = j
c[j+1] = 0)
E2 ; Visit
(funcall visit (vectorToList a))
E3 ; Find k
k = 1
(when (c[k] == k)
(do_until (c[k] < k)
c[k] = 0
k++))
(if (k == n)
(return)
c[k] = c[k] + 1)
E4 ; Swap
a[0] = (prog1 a[b[k]]
a[b[k]] = a[0])
E5 ; Flip
j = 1
k
(while (j < k)
;; swap b[j] and b[k]
b[j] = (prog1 b[k]
b[k] = b[j])
j++
k)
(go E2))))
Permutation generation by cyclic shifts
The following implements algorithm C (Permutation generation by cyclic
shifts) from Donald E. Knuth, The Art of Computer Programming
Volume 4 Fascicle 2, Generating All Tuples and Permutations, page
56.
(defun map_permutations_C (visit data "ul")
(letseq ((x (listToVector (cons nil data)))
(n (length data))
a
k
j)
(prog ()
C1 ; Initialize
a = (listToVector (cons nil data))
C2 ; Visit
(funcall visit (cdr (vectorToList a)))
k = n
C3 ; Shift
;; (a1 a2 a3 ..ak) < (a2 a3 ...ak a1)
a[k] = (prog1 a[1]
(for j 1 k1
a[j] = a[j+1]))
(when (a[k] != x[k])
(go C2))
C4 ; Decrease k.
k
(when (k > 1)
(go C3)))))
Summary
In this article we looked at several things.
 Four functions for visiting all permutations of a given list.
Feel free to copy and paste these implementations into your SKILL
programs, but please remember to give credit to Donald Knuth where
appropriate.
map_permutations_BF
 Brute force
map_permutations_C
 Cyclic shifts
map_permutations_P
 Plain changes
map_permutations_E
 Ehrlich swaps
 Translating algorithms from Donald Knuth's Art of Computer Programming to SKILL
 Seldom used features of SKILL
(prog ...)
such as (go ...)
 Examples using
makeVector
, listToVector
,
and vectorToList
.
See Also