5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Martin Buchmann May 1 '17 at 11:33
  • \$\begingroup\$ @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. \$\endgroup\$ – Rainer Joswig May 1 '17 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.