自然数の分割 in Scheme DouKaku?

自然数nとm(n>=m>0)が与えられたとき，nをm個の非負の整数の和で表すやり方を全て出力してください．
その際，和の組(x_1, ..., x_m)は大きい順に出力してください．
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします．

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する．

Schemeならsrfi-42でcomprehensionが使えます。

(use srfi-42)

(define (partition-num n m)
  (if (= m 1)
    `((,n))
    (list-ec (: x 0 (+ n 1)) (: xs (partition-num x (- m 1)))
             (cons (- n x) xs))))

n=5 m=3 の場合、

(reverse (list-ec (: a 6) (: b 6) (: c 6) (if (= 5 (+ a b c))) (list a b c)))

というコードが生成されれば良い。

→マクロで書いてみる。

→nとmがコンパイル時に決まらないから無理？

→生成したコードをevalする方針に変更。

とこんな風になりました。

;; comprehensionと再起の組み合わせであんなに短く書けるとは。

(use srfi-1)
(use srfi-42)

(define (quolifiers upper-bound n-quos)
  (let1 gensyms (map (lambda (x) (gensym)) (iota n-quos))
    (values gensyms
            (map (lambda (sym) `(: ,sym ,upper-bound))
                 gensyms))))

(define (partition-num n m)
  (receive (syms form) (quolifiers (+ n 1) m)
    (eval `(reverse (list-ec ,@form (if (= ,n (+ ,@syms))) (list ,@syms)))
          scheme-report-environment)))

リストのネスト具合の辻褄合わせが大変だった。静的型言語ならコンパイルするだけでチェックできるのに……

(use util.match)

(define-constant USAGE
  (string-join '("usage: command n m"
                 "       n, m -> positive integer (n >= m > 0)") "\n"))

(define (split-num_ base n m acc)
  (cond ((= m 0) `((,n)))
        ((< n 0) acc)
        (else
          (let* ((base_ (- base n))
                 (sub   (split-num_ base_ base_ (- m 1) '()))
                 (acc_  (map (pa$ cons n) sub)))
            (split-num_ base (- n 1) m (append acc_ acc))))))

(define (split-num n m)
  (cond ((not (and (>= n m) (> m 0))) (print USAGE))
        (else
          (let* ((nums (split-num_ n n (- m 1) '()))
                 (lines (map (lambda (lst)
                               (string-join (map number->string lst) ", " 'suffix))
                             nums))
                 (sorted (sort lines (lambda (a b) (compare b a)))))
            (string-join sorted "\n")))))

(define (main argv)
  (match argv
         ((_ n m)
          (print (split-num (string->number n) (string->number m))))
         (_ (print USAGE))))

DouKaku?

自然数の分割

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq