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