# Calculation of lexicographic permutations

Just for fun, I studied the generation of lexicographic permutations and came across the following algorithm which I transcribed into Common Lisp, as good as I can, being a hobbyist:

(defun lexicographic-permutation% (order n)
"Returns the Nth permutation of integers from 0 upto order."
(let* ((range (loop :for i :upto order :collect i))
(len (1+ order))
(permutation (make-array len :initial-contents range)))
(loop :while (< count n)
:for count :from 1
:for i = order
:for j = len
:do
(loop :while (>= (aref permutation (1- i))
(aref permutation i))
:do (decf i))
(loop :while (<= (aref permutation (1- j))
(aref permutation (1- i)))
:do (decf j))
(rotatef (aref permutation (1- i))
(aref permutation (1- j)))
(incf i)
(setf j len)
(loop :while (< i j)
:do (rotatef (aref permutation (1- i))
(aref permutation (1- j)))
(incf i)
(decf j))
:finally (return permutation))))


While it is working and fast I am unsure about the explicit side-effects using setf and incf and the structure of the loops. I know that Common Lisp is not a strict functional language and allows several paradigmas which is considered to be an advantage. But I was asking myself if the algorithm could be written in a clearer idiom in CL.

I was thinking about packing the rotatef-pattern in an extra function which could be inlined. But this is not really what I am worried about, s. above. Furthermore the usage of loop itself is fine for me, because I like its DSL.

LOOP syntax violation

There is a LOOP syntax violation: your LOOP starts with a WHILE clause and FOR clauses follow. This is not allowed according to the ANSI CL LOOP syntax. WHILE is a main clause, which follow after the variable clauses.

WHILE is not needed

The while...for... is just a for.

LOOP iterations in the sub-LOOPs are creating side-effects

I would propose to rewrite the sub-LOOPS to return values. That would make it easier to refactor them into functions.

I tried to keep the main loop small and remove the side-effects. If the function calls are too much overhead, we could let Lisp inline them with a INLINE declaration.

Each of the sub-functions have a purpose and can be described and tested separately.

(defun lexicographic-permutation% (order n &aux (len (1+ order)))
"Returns the Nth permutation of integers from 0 upto order."
(labels ((iota (n)
(loop :for i :upto n :collect i))
(compute-i (permutation order)
(loop :for i :downfrom order
:when (< (aref permutation (1- i))
(aref permutation i))
:do (return i)))
(compute-j (permutation len i)
(loop :for j :downfrom len
:when (> (aref permutation (1- j))
(aref permutation (1- i)))
:do (return j)))
(swap-ij (permutation i j)
(rotatef (aref permutation i) (aref permutation j)))
(swap (permutation i j)
(loop :for i1 :from i :and j1 :downfrom j
:while (< i1 j1)
:do (swap-ij permutation (1- i1) (1- j1)))))
(let ((permutation (make-array len :initial-contents (iota order))))
(loop :for count :from 1 :upto n
:for i = (compute-i permutation order)
:for j = (compute-j permutation len i)
:do
(swap-ij permutation (1- i) (1- j))
(swap    permutation (1+ i) len))
permutation)))

• That is exactly what I was looking for and very inspiring! I guess you have chosen labels because of the recursive call of swap-ij in swap. Is it considered to be bad style to have an flet and labels block within the same function? – Martin Buchmann May 1 '17 at 11:33
• @MartinBuchmann: yes, the functions might be used in other local functions. One could use an FLET and a LABELs part, but the advantage in intent over code complexity is not huge. – Rainer Joswig May 1 '17 at 14:09