全排列、求子集、map实现

;;(1 2 3)
;;(() (2) (3) (2 3))
;;((1) (1 2) (1 3) (1 2 3))
(defun power-set (sequence)
  (cond ((null sequence)
         (list '()))
        (t (apply 'append (power-set (cdr sequence))
                  (mapcar (lambda (x) (list (cons (car sequence) x))) (power-set (cdr sequence)))))))

(defun power-set (sequence)
  (cond ((null sequence)
         (list '()))
        (t (let ((subset (power-set (cdr sequence))))
               (apply 'append subset
                  (mapcar (lambda (x) (list (cons (car sequence) x))) subset))))))

(length (power-set '(1 2 3 4 5 6 7 8)))

;;E(a b c) = aE(b c) + bE(a c) + cE(a b)
;;            = a( bE(c) + cE(b)) + b(aE(c) + cE(a)) + c(aE(b) + bE(a))
;;
(defun permute (sequence)
  (cond ((null sequence)
         '(()))
        (t (apply 'append (mapcar (lambda (elem)
                                   (mapcar (lambda (permutesub)
                                          (cons elem permutesub)) (permute (remove elem sequence)))) sequence)))))

(permute '(1 2 3))

(defun map-unarry (fn seq)
  (if (null seq)
      '()
      (cons (funcall fn (car seq)) (map-unarry fn (cdr seq)))))

(mapcar 'car '((1 2) (3 4) (5 6 7)))

(defun my-map (fn first-list &rest other-list)
  (if (null first-list)
      '()
      (cons (apply fn (cons (car first-list) (map-unarry 'car other-list)))
            (apply 'my-map (cons fn (cons (cdr first-list) (map-unarry 'cdr other-list)))))))

(my-map 'cons '((0 1) 2) '(3 4) )
(my-map '* '(1 2) '(3 4) '(5 6) '(7 8))