Calculation of lexicographic permutations

Question

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.

Answer 1

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.

My version of your code

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)))

• Martin Buchmann: 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?
• Rainer Joswig: @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.