順列の列挙 - 象徴ヶ淵

順列を列挙する関数が野暮用で必要になったが、すぐに書けなかったので書き方を調べた。要素を木構造にして深さ優先探索(DFS)で書けば良いらしい。簡単だね！

(defun permutation (args &optional num head res)
  (labels ((iter (args num head res)
             (if (and (plusp num) args)
                 (let (l)
                   (dotimes (i (length args) (apply 'nconc (nreverse l)))
                     (push (iter (nconc (subseq args 0 i) (subseq args (1+ i))) (1- num)
                                 (append head (list (elt args i))) res) l)))
               (nconc res (list head)))))
    (iter args (or num (length args)) nil nil)))

; N<5に対して実行するとき 6!=720, 7!=5040 8!=40320, 9!=362880 に注意しよう。
*(permutation '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

*(permutation '(1 2 3 4) 2)
((1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3))

おまけ

組み合わせの列挙。ほぼ同じ形で、前に登場した要素を使わなければ良いだけ。

(defun combination (args &optional num head res)
  (labels ((iter (args num head res)
             (if (and (plusp num) args)
                 (let (l)
                   (dotimes (i (- (length args) num -1) (apply 'nconc (nreverse l)))
                     (push (iter (subseq args (1+ i)) (1- num)
                                 (append head (list (elt args i))) res) l)))
               (nconc res (list head)))))
    (iter args (or num (length args)) nil nil)))

*(combination '(1 2 3 4 5) 2)
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))