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)))