魔方分割数 in Scheme DouKaku?

1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。

ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。

なお、数え上げるときの注意として、

・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの

・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
　{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。

filterとcombinationsを覚えた

;Pen4 3GHzで
;(time (maho 4)) => 392
;real 0.109/user 0.109/sys 0.000
;(time (maho 5)) => 3245664
;real 1528.250/user 1423.391/sys 104.187
;(time (maho-by-enm 4)) => 392
;real 254.094/user 249.000/sys 1.531

maho-by-enmは#4819や#4821と同じ方法です

(use srfi-1)
(use util.combinations)
(define (maho n)
  (define (maho-in m l)
    (if (= m 0) 1
      (letrec
       ((cn (/ (* n (+ (* n n) 1)) 2))
        (mylist
         (map (lambda (li) (cons (car l) li))
              (filter
               (lambda (li) (= (apply + li) (- cn (car l))))
               (combinations (cdr l) (- n 1))))))
       (apply + (map (lambda (a) (maho-in (- m n) (lset-difference equal? l a))) mylist)))))
  (maho-in (* n n) (iota (* n n) 1)))

(define (maho-by-enm n)
  (define (center n) (/ (* n (+ (* n n) 1)) 2))
  (define (flatten2 l c)
    (define (flatten1 l c)
      (if (null? l) c
        (cons (car l) (flatten1 (cdr l) c))))
    (if (null? l) c
      (flatten2 (cdr l) (flatten1 (car l) c))))
  (define (my-equal? l1 l2)
    (null? (lset-xor eq? (flatten2 l1 '()) l2)))
  (define (enm-n n)
    (filter (lambda (l) (= (apply + l) (center n)))
            (combinations (iota (* n n) 1) n)))
  (filter (lambda (l) (my-equal? l (iota (* n n) 1)))
          (combinations (enm-n n) n)))

同じ計算を何回もしているので#1671を参考にメモ化しました.
n=5で2分と少々です. メモリ使用量は11MB (多分).
Pen4 3GHzです.

gosh> ;(time (maho-memo 4))
; real   0.078
; user   0.078
; sys    0.000
392
gosh> ;(time (maho-memo 5))
; real 130.656
; user 124.562
; sys    4.828
3245664

see: どう書く？org #1671 shiro: メモ化をちょっと試してみた。単純にn...(「組合せ型の最小完全ハッシュ関数」の逆関数)

(define (maho-memo n)
  (define cn (/ (* n (+ (* n n) 1)) 2))
  (define maho-in-memo
    (let1
     tab (make-hash-table 'equal?)
     (define (memo m l v) (hash-table-put! tab (cons m l) v) v)
     (lambda (m l)
       (cond ((= m 0) 1)
             ((hash-table-get tab (cons m l) #f))
             (else
              (memo m l
                    (apply
                     +
                     (map
                      (lambda (a) (maho-in-memo (- m n) (lset-difference equal? l a)))
                      (map
                       (lambda (li) (cons (car l) li))
                       (filter
                        (lambda (li) (= (apply + li) (- cn (car l))))
                        (combinations (cdr l) (- n 1))))))))))))
  (maho-in-memo (* n n) (iota (* n n) 1)))

無駄な計算を省いて1分切ったので再投稿

gosh>
;(time (maho-memo 5))
; real  43.391
; user  42.625
; sys    0.641
3245664

(use srfi-1)
(use util.combinations)

(define (maho-memo n)
  ;tableに足してcnになるリストを入れておく
  (define table 
    (let ((cn (/ (* n (+ (* n n) 1)) 2)))
      (filter
       (lambda (li) (= (apply + li) cn))
       (combinations (iota (* n n) 1) n))))
  (define maho-in-memo
    (let1
     tab (make-hash-table 'equal?)
     (define (memo m l v) (hash-table-put! tab (cons m l) v) v)
     (lambda (m l)
       (cond ((= m 0) 1)
             ((hash-table-get tab (cons m l) #f))
             (else
              (memo m l
                    (apply
                     +
                     (map ; 今のlからaを除いたリストでmaho-in-memoを呼ぶ
                      (lambda (a) (maho-in-memo (- m n) (lset-difference equal? l a)))
                      (filter ;(car l)で始まるtableの中のリストを抜き出す
                       (lambda (li) (and (equal? (car li) (car l)) (lset<= equal? li l)))
                       table)))))))))
  (maho-in-memo (* n n) (iota (* n n) 1)))
(time (maho-memo 5))

DouKaku?

魔方分割数

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq