; 親子ペア定義
(setf pair-lst '((a b)
                 (b c)
                 (c d)
                 (c e)
                 (a f)
                 (d x)
                 (y z)
                 (z c)
                 ))

;; 同一の親を持つペアをマージする
;; ex) ((p1 c1) (p1 c2) (p2 c3) (p2 c4)) -> ((p1 c1 c2) (p2 c3 c4))
(defun gen-fmly-lst (plst)
  (defun merge-lst (frst rst)
    (if (null rst)
      frst
      (if (eq (car frst) (caar rst))
        (merge-lst (append frst (cdar rst)) (cdr rst))
        (merge-lst frst (cdr rst)))))
  (labels ((rec (lst acc)
                (if (null lst)
                  acc
                  (if (member (caar lst) acc :key #'car)
                    (rec (cdr lst) acc)
                    (rec (cdr lst) (cons (merge-lst (car lst) (cdr lst)) acc))))))
    (rec plst nil)))

;; fmlyのリストからツリーを生成する
(defun gen-fmly-tr (fmly-lst)
  (labels ((rec (flst acc)
                (if (null flst)
                  acc
                  ; hook前のfmlyをhook後のfmly(n次元リスト)に置き換えて処理をする
                  (let* ((nD-fmly (car (member (caar flst) acc :key #'car)))
                         (othr (other nD-fmly acc)))
                    ; fmlyをhook処理し、一箇所もhookできなかったらfmlyをそのままaccに加える
                    (if (equal othr (hook nD-fmly othr))
                      (rec (cdr flst) (cons nD-fmly othr))
                      (rec (cdr flst) (hook nD-fmly othr)))))))
    (rec fmly-lst fmly-lst)))

;; リストからobjを除いたリストを取得する
(defmacro other (obj lst)
  `(remove-if #'(lambda (x) (equal ,obj x)) ,lst))

;; リストのcarと一致するatomをツリーの中で見つけた場合、該当atomをリストで置き換える
;; ex) (hook '(a x) '(a (b a) (c (d a)))) -> ((a x) (b (a x)) (c (d (a x))))
(defun hook (lst tree)
  (cond ((eq (car lst) tree) lst)
        ((atom tree) tree)
        (t (cons (hook lst (car tree))
                 (hook lst (cdr tree))))))

(defun main ()
  (gen-fmly-tr (gen-fmly-lst pair-lst)))
; 実行すると、下記の構造が得られる
; ((A (B (C (D X) E)) F) (Y (Z (C (D X) E))))
; インデントすると
;((A
;   (B
;     (C
;       (D
;         X)
;       E))
;   F)
; (Y
;   (Z
;     (C
;       (D
;         X)
;        E)))
; )