permutations.lisp

; Heap's algorithm
; ref. https://ja.wikipedia.org/wiki/Heap%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
(defun %permutations (a)
  (let* ((n (length a))
         (c (make-array n))
         (i 0)
         (caller nil)
         (firstp nil))
    (setf caller
          (lambda ()
            (cond ((not firstp) (setf firstp t)
                                a)
                  ((<= n i) nil)
                  ((<= i (aref c i)) (setf (aref c i) 0)
                                     (incf i)
                                     (funcall caller))
                  (t (if (evenp i)
                         (rotatef (aref a 0)  (aref a i))
                         (rotatef (aref a (aref c i))  (aref a i)))
                     (incf (aref c i))
                     (setf i 0)
                     a))))
    caller))

; example
(loop :with generator := (%permutations #(0 1 2 3))
      :with a := (funcall generator)
      :do (format t "~A~%" a)
      :while (setf a (funcall generator)))
;; #(0 1 2 3)
;; #(1 0 2 3)
;; #(2 0 1 3)
;; #(0 2 1 3)
;; #(1 2 0 3)
;; #(2 1 0 3)
;; #(3 1 0 2)
;; #(1 3 0 2)
;; #(0 3 1 2)
;; #(3 0 1 2)
;; #(1 0 3 2)
;; #(0 1 3 2)
;; #(0 2 3 1)
;; #(2 0 3 1)
;; #(3 0 2 1)
;; #(0 3 2 1)
;; #(2 3 0 1)
;; #(3 2 0 1)
;; #(3 2 1 0)
;; #(2 3 1 0)
;; #(1 3 2 0)
;; #(3 1 2 0)
;; #(2 1 3 0)
;; #(1 2 3 0)