Home > Community > Blogs > Custom IC Design > skill for the skilled visiting all permutations

 Login with a Cadence account. Not a member yet? Create a permanent login account to make interactions with Cadence more convenient. Register | Membership benefits
 Get email delivery of the Custom IC Design blog (individual posts).

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

# SKILL for the Skilled: Visiting All Permutations

Comments(0) 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 N-k 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 pseudo-code 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 Knuth-friendly feature of SKILL `prog` but not the SKILL++ `prog` is that it allows top-level 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 j-c[j]+s)
(v j-q+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 in-keeping with the Knuth algorithm. Converting between list and array is done using `listToVector` and `vectorToList`.

Zero indexed vs. one indexed
SKILL only provided zero-based arrays. Some of the Knuth algorithms use one-based and some used zero-based arrays. Where appropriate, filler elements are used for the 0th element when the Knuth array is one-based. You'll see expressions such as `(funcall visit (cdr (vectorToList a)))` in the SKILL implementations, which means the corresponding array is one-based 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 zero-indexed and one-indexed arrays.

allocatearray to listlist to array
N element
zero-indexed
`(makeVector N)``(vectorToList myarr)``(listToVector mylist)`
N element
one-indexed
`(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 re-evaluating 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 n-1
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 k-1
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`.