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 (= (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.

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

StackExchange Code Review Q#162178, answer score: 2