P27: リストをグループ分けする

P27はリストをグループ分けする問題。
P26で定義したcombinationを流用する。
まずは、9要素のリストを2 3 4の要素に分割する関数 group3をつくる。
その後に、分割パターンをリストとして受け取る関数 groupをつくる。

groupは、順番が違うだけで、実質同じグループ分けも答えに含めてしまっている。

;; P27
(defun combination/rest (n list)
  (let ((results (combination n list)))
    (list results
	  (mapcar (lambda (result)
		    (remove-if (lambda (elem)
				 (member elem result)) list)) results))))

(combination/rest 2 '(a b c d))
;; => (((A B) (A C) (A D) (B C) (B D) (C D)) ((C D) (B D) (B C) (A D) (A C) (A B))) 


(defun group3 (list)
  (apply #'append
	 (apply #'mapcar (lambda (group1 rest1)
			   (apply #'mapcar (lambda (group2 rest2)
					     (list group1 group2 rest2)) (combination/rest 3 rest1)))
		(combination/rest 2 list))))

(length (group3 '(a b c d e f g h i)))
;; => 1260 (#x4EC, #o2354, #b10011101100)

(defun group (lis split)
  (cond
   ((null split) (list (list lis)))
   (t
    (apply #'nconc
	   (apply #'mapcar (lambda (group1 rest)
			     (if rest
				 (mapcar (lambda (result)
					   (append (list group1) result))
					 (group rest (cdr split)))
			       (list (list group1))))
		  (combination/rest (car split) lis))))))

(group '(a b c d) '(2 1 1))
;;=> (((A B) (C) (D)) ((A B) (D) (C)) ((A C) (B) (D)) ((A C) (D) (B))
;;    ((A D) (B) (C)) ((A D) (C) (B)) ((B C) (A) (D)) ((B C) (D) (A))
;;    ((B D) (A) (C)) ((B D) (C) (A)) ((C D) (A) (B)) ((C D) (B) (A)))