Ex4.2 順列の生成

リストを取って、その全ての順列を生成する関数を定義する。

;; Exercise 4.2[m] Write a function that generates all permutations of its input.
(defun map/rest (func list &optional (acc nil) (results nil))
  (if (null list)
      results
      (map/rest func (cdr list) (cons (car list) acc)
		(cons (funcall func (car list) (append acc (cdr list))) results))))

(defun permutations (list)
  (cond
   ((null list) nil)
   ((null (cdr list)) (list list))
   (t (apply #'nconc
	     (map/rest (lambda (elem rest)
			 (mapcar (lambda (result)
				   (cons elem result)) (permutations rest))) list)))))

(length (permutations '(1 2 3 4 5 6 7 8 9 10)))
;; => 3628800 (#x375F00, #o15657400, #b1101110101111100000000)
(permutations '(1 2 3 4))
;; => ((4 1 3 2) (4 1 2 3) (4 2 1 3) (4 2 3 1) (4 3 1 2) (4 3 2 1) (3 4 2 1)
;;     (3 4 1 2) (3 1 4 2) (3 1 2 4) (3 2 4 1) (3 2 1 4) (2 4 1 3) (2 4 3 1)
;;     (2 3 4 1) (2 3 1 4) (2 1 4 3) (2 1 3 4) (1 4 2 3) (1 4 3 2) (1 3 4 2)
;;     (1 3 2 4) (1 2 4 3) (1 2 3 4))