分割数・続き - ishikawashの学習ノート

自然数を[分割]して得られた数列を各要素と同じ数だけ点を並べて表現してみよう。例えば、 14 = 6 + 4 + 3 + 1 をこのルールに従って表現すると次のようなパターンができる。

●●●● 
●●●
●●●
●●
●
●

このように分割を複数の点で視覚化したパターンのことを[Ferrers Graph]と呼ぶ（Graphと言っても一般的なグラフとは異なるので、区別してFerrers Diagramと言う場合もある）。ちなみにFerrers Graphとは、19世紀のイギリスの数学者[Norman Macleod Ferrers]にちなんで名付けられたそうだ。

ある分割のFerrers Graphを転置して得られる分割を[Conjugate Partition]と言う。例えば、先程挙げた6 + 4 + 3 + 1を転置すると、新たに4 + 3 + 3 + 2 + 1 + 1という分割を得る。

●●●●
●●●
●●●
●●
●
●
↓
●●●●●●
●●●●
●●●
●

なお、転置しても同じパターンが得られる分割を[Self-Conjugates-Partition]と呼ぶ。このSelf-Conjugates-Partitionは、実際にパターンを書くと分かる通り、左上頂点を原点として y = -x に線対称な図形を作る。例えば、8からは 4 + 2 + 1 + 1 と 3 + 3 + 2 の2通りのSelf-Conjugates-Partitionが得られる。

● ● ● ●
● ●
●
●

● ● ●
● ● ●
● ●

私は数学に関して全くの素人なのでこれ以上の考察はできないが、単純なルールによって分割された自然数の中にこのような対称性が潜んでいる事を知って大変興味深い。

さて、最後にSelf-Conjugates-Partitionをプログラムで求めてみる。以下、Schemeによるコード。

(use gauche.collection)
(use srfi-1)

(define (partition-of n)
  (let loop ((x 1) (result '()))
    (if (> x n)
	result
	(loop (+ x 1)
	      (append (partition-f n x) result)))))

(define (partition-f n k)
  (cond ((or (<= n 0) (< n k)) '())
	((= n k) (cons (list k) '()))
	(else 
	  (fold (lambda (x s1)
		      (append
 		        (fold (lambda (ls s2) (cons (cons k ls) s2))
			      '()
			      (partition-f (- n k) x))
			s1))
		'()
		(filter (lambda (x) (<= x k)) (iota (- n k) 1))))))

(define (memoize proc)
  (let ((cache (make-hash-table 'equal?)))
    (lambda (arg . rest)
      (let ((args (cons arg rest)))
	(let ((computed-result (hash-table-get cache args #f)))
	  (or computed-result
	      (let ((result (apply proc args)))
		(hash-table-put! cache args result)
		result)))))))

(define (fast-partition-of n)
  (let loop ((x 1) (result '()))
    (if (> x n)
	result
	(loop (+ x 1)
	      (append (fast-partition-f n x) result)))))

(define fast-partition-f
  (memoize
   (lambda (n k)
     (cond ((or (<= n 0) (< n k)) '())
	   ((= n k) (cons (list k) '()))
	   (else 
	    (fold (lambda (x s1)
		    (append
		     (fold (lambda (ls s2) (cons (cons k ls) s2))
			   '()
			   (fast-partition-f (- n k) x))
		     s1))
		  '()
		  (filter (lambda (x) (<= x k)) (iota (- n k) 1))))))))

(define (merge proc ls1 ls2)
  (letrec ((loop
	     (lambda (result first second)
	       (if (null? first)
		   (append result second)
		   (loop (cons (proc (car first) (car second)) result)
			 (cdr first) (cdr second))))))
    (if (< (length ls1) (length ls2))
	(loop '() ls1 ls2)
	(loop '() ls2 ls1))))

(define (conjugate-of partition)
  (letrec ((loop
	     (lambda (ls result)
	       (if (null? ls)
		   result
		   (loop (cdr ls) (merge + (car ls) result))))))
    (if (null? partition)
	'()
	(loop 
 	  (fold (lambda (x result)
		  (append (fast-partition-f x 1) result))
		'()
		(reverse partition))
	  '()))))

(define (self-conjugates-of n)
  (filter (lambda (p) (equal? p (conjugate-of p))) (partition-of n)))

今回のエントリーを書くにあたって分割関数のアルゴリズムを見直したら前よりずっと速くなった。多分もっと速いアルゴリズムがあるのだろうけど、そろそろ次の話題に移りたいのでこの辺で。

% gosh partition-numbers-old.scm 20
;(time (partition-f n))
; real  17.101
; user  14.410
; sys    0.350

% gosh partition-numbers.scm 20    
;(time (partition-of n))
; real   0.104
; user   0.080
; sys    0.000