読者です 読者をやめる 読者になる 読者になる

Project おいら

programming scheme

Project Eulerにあらず。自分で思いついた問題を自分で解く試み。
というか、偶然直面した問題を、抽象化して手を加えたらパズルのような問題になったので、とりあえず解いてみたってだけ。

非負整数を1個以上の0以上(または1以上)の整数の和の形で表す表し方の総数を求める問題とか、実際にどういう形で表すことができるのかを求める問題はよくあることと思う。これに「分割の個数」と「上限値」という制限を付け加えたらどうなるか。
より正確には、(val,num,max-valを与えられた正整数として)num個の整数列x[i] (1 <= x[i] <= max-val)のうちで、x[0] + x[1] + … + x[num-1] = val となるものを無作為に1つ返すような関数を定義せよ、という問題。

(random-partition 10 3 5) ;=> (5 4 1)
(random-partition 20 4 7) ;=> (5 6 3 6)
(random-partition 20 5 5) ;=> (4 1 5 5 5)

のrandom-partitionみたいな関数を求めましょう。


で、ソースコード

(require (lib "1.ss" "srfi")
         (lib "27.ss" "srfi"))

(define (random-between m n)
  (+ m (random-integer (- n m -1))))

(define (random-partition val num max-val)
  (cond
    [(= num val)
     (make-list num 1)]
    [(= (* num max-val) val)
     (make-list num max-val)]
    [(and (< val max-val) (= num 1))
     (list val)]
    [else
     (let ((n (- num 1)))
       (define (next v)
         (cons v (random-partition (- val v) n max-val)))
       (cond
         [(< (- val max-val) n)
          (next (random-between 1 (- val n)))]
         [(< (* n max-val) (- val 1))
          (next (random-between (- val (* n max-val)) max-val))]
         [else
          (next (random-between 1 max-val))]))]))

次のように実行する。

> (random-partition 10 4 5)
(2 3 3 2)
> (random-partition 10 4 5)
(3 3 3 1)
> (random-partition 10 4 5)
(3 4 1 2)
> (random-partition 10 4 5)
(2 1 5 2)
>

なんか煩雑そうなコードになった。それは、1つには、num <= val <= num * max-val という不変条件が成り立つように、上にも下にも気をつけながら再帰をしなければいけないことによるんだと思う。いや、できる人がやればもっと綺麗にできるのかもしれないけど。
たとえば、

(define (random-partition val num max-val)
  (map + (random-partition-aux (- val num) num (- max-val 1))
         (make-list num 1)))

とかすれば、random-partition-auxは不変条件が 0 <= val <= num * max-val の問題になるから、もうちょっと綺麗に書けるはず。あるいは、もっと根本的に違うやり方もあるのかもしれない。