L-99 P58

久々のプログラミングネタです。
L-99: Ninety-Nine Lisp Problems の P58 です。

P58

Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
Example:

sym-cbal-trees(5,Ts).

Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]

How many such trees are there with 57 nodes?
Investigate about how many solutions there are for a given number of nodes?
What if the number is even?
Write an appropriate predicate.

Q1 ノードが 57 個のとき、シンメトリーな木のパターンはいくつありますか？

これはまともに木と作っていたのでは解けない問題です。

いつものようにエクセル先生に計測結果のデータをはっつけて傾向と対策を探ります。
事象を計測し、データを集め、法則性を導き出します。物理測定的な解法アプローチです。

;; シンメトリになる木の形状数とノード数の関係

;; A ... 木が完全に釣り合い、かつ底辺の部分のノードが全てそろっているときの底辺のノード数
;; B ... A の補完用の数
;; C ... ノードの総個数
;; D ... シンメトリな木がいくつ出来るかの数

;;  A   B     C          D

;;  1         1          1
;;  2         3          1    
;;      3     5        2C1
;;  4         7          1    
;;      5     9        4C1
;;      6    11        4C2
;;      7    13        4C3
;;  8        15          1    
;;      9    17        8C1
;;     10    19        8C2
;;     11    21        8C3
;;     12    23        8C4
;;     13    25        8C5
;;     14    27        8C6
;;     15    29        8C7
;; 16        31          1    
;;     17    33       16C1
;;     18    35       16C2
;;     19    37       16C3
;;     20    39       16C4
;;     21    41       16C5
;;     22    43       16C6
;;     23    45       16C7
;;     24    47       16C8
;;     25    49       16C9
;;     26    51      16C10
;;     27    53      16C11
;;     28    55      16C12
;;     29    57      16C13  
;;     30    59      16C14
;;     31    61      16C15
;; 32        63          1    
;; ...

こうなります。
このように書き出す事で、法則性があることが簡単にわかります。

ではプログラムを書いていきましょう。
まず組み合わせを計算する手続きを定義します。

(define (fact n x)
  (if (= n 0)
      x
      (fact (- n 1) (* n x))))

(define (perm n r)
  (/ (fact n 1) (fact (- n r) 1)))

(define (comb n r)
  (/ (perm n r) (fact r 1)))

もっと最適化したほうが良い気がしますが、とりあえずこれで良いです。

次に sym-cbal-trees 手続きを定義します。

(define (sym-cbal-trees num)
  (if (even? num)
      0
      (let ((node (log (ceiling (/ num 2)) 2)))
	(if (integer? node)
	    1
	    (let* ((n (expt 2 (x->integer (floor node))))
		   (r (/ (- num (- (* n 2) 1)) 2)))
	      (comb n r))))))

評価してみます。

gosh> (sym-cbal-trees 57)
560

ノードが 57 個ある場合のシンメトリーな木のパターン数は 16C13 = 560 通りあります。

gosh> (time (sym-cbal-trees 9999))
;(time (sym-cbal-trees 9999))
; real   0.031
; user   0.016
; sys    0.016
11436577103049044761221198452518585133677289942544128222443208541369564296810237881125967457185479641859012730749157186026337918310836632184920317429918436832010257712575772912316220048781763180094007260818057119503806472024206237596484037000140955340252760462967607750042611650203259940138602730532492794523053088567877493404920122261243367706161155208567426628443813443651696627343049842580327429128644640369480496760583320982834694512737735411260748844111840176823690848814303441663535288847068276026265786809416498272260267278458991790785446499622063519550479432824371337083954743633428654825784779186826178487299263070808528918377649365725029528130681578375288057135466767026007948970298778625485276413177715104731228883683342449139314942649780402785046948110513608918309676805587816441279133004480534189254221248137175247422703164594490199643957079542420945088581088725822489773787042972410242180451209340578022707144445821125127680

ノードが 9999 個の場合もすぐ求まります。
巨大な数字すぎて読み方がわかりませんが、これだけの組み合わせがあります。

Q2 ノード数が偶数の場合はどうなりますか？

ノード数が偶数の場合は、シンメトリーな木は作れません。ノード数が偶数の場合は、0 通りです。