第8夜:いったい何通りあるの？
数の悪魔*1を題材にして、プログラミングの勉強中。その8回目。階乗と組合せです。
「アルファベット順がいい」。ドリスが言った。「アルバートAlbertがAで、ベッティーナBettinaがBで、チャーリーCharlieがCで、ドリスDorisがD。一番簡単でしょ。」「まあ、いいか。じゃ、やってみるとしよう」ロバートは黒板にこんなふうに書いた。
(define (combination cl)
(define (combi-loop c l nl)
(define (move-person p q nl)
(if (null? q)
(cons (reverse (cons c p)) nl)
(move-person
(cons (car q) p)
(cdr q)
(cons (append p (cons c q)) nl))))
(if (null? l)
nl
(combi-loop c (cdr l) (move-person '() (car l) nl))))
(define (combi-iter cl nl)
(if (null? cl)
nl
(combi-iter (cdr cl) (combi-loop (car cl) nl '()))))
(combi-iter cl '(()))
)
(define (main args)
(print (combination '("A" "B" "C" "D")))
0)本のとおりにAにBを前後に加えて、さらにCを前、真ん中、後ろ、というように移動させてパターンを作ってます。勢いでcombinationと名前をつけてしまいましたが、実はfactorialだったりします(やっちゃったZe☆)。
結果は以下のとおり。並びの頭をABCDにしようとしたらもう一回appendが必要になってしまったので、順序はばらばらのままにしました。うまくやる方法があるかもしれません。
((C A B D) (A C D B) (C D A B) (D C A B) (A C B D) (C A D B) (A D C B) (D A C B) (A B C D) (B A D C) (A D B C) (D A B C) (C B A D) (B C D A) (C D B A) (D C B A) (B C A D) (C B D A) (B D C A) (D B C A) (B A C D) (A B D C) (B D A C) (D B A C) )
本では更に、n人の人が握手するパターンの数C(n,2)が三角数と同じになるなど組合せについて書かれています。
それでは最後に、ウルフラム・アルファさんに聞いてみよう:http://www.wolframalpha.com/input/?i=4%21
