自然数の分割 in OCaml 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,
を出力する．

#4344 の移植。エラー処理はあまり意味が無いので省いた。あと、sort とかいらなかったので、これも削除。 (当初は、完全に末尾再帰にしようと思っていて、その時点では順番が崩れるだろうという予想だったんですが……)

rev_map や rev_append でリストの方向がころころ変わってる辺りが OCaml らしいと言えばらしいところ。

let rec split_num' base n m acc =
   match n, m with
   | _, 0 -> [[n]]
   | n, _ when n < 0 -> acc
   | n, m ->
        let base' = base - n in
        let sub   = split_num' base' base' (pred m) [] in
        let acc'  = List.rev_map (fun xs -> n::xs) sub in
        split_num' base (pred n) m (List.rev_append acc' acc)

let split_num n m =
   let nums  = split_num' n n (pred m) [] in
   let lines =
      List.rev_map begin fun lst ->
         String.concat ", " (List.map string_of_int lst)
      end nums
   in
   String.concat "\n" lines

let main () =
   match Sys.argv with
   | [|_; n; m|] ->
        print_endline (split_num (int_of_string n) (int_of_string m))
   | _ ->
        print_endline "usage: command m n"

let () = if not !Sys.interactive then main ()

ざっくり書きました。upto みたいなのは標準ライブラリにあるのかな。それから cons を関数として使おうとして (::) と書いてみたのですが、構文エラーになってしまいました。はて。

open List

let upto x =
  let rec upto' y =
    if x=y then
      [y]
    else
      y :: upto' (y+1)
  in upto' 0
let cons x y = x::y
let rec bunkatu n m =
  if m <= 1 then 
    [[n]]
  else
    let cand = map (fun x -> (x,n-x)) (upto n) in
      concat (map (fun (a,b) -> map (cons a) (bunkatu b (m-1))) cand)

DouKaku?

自然数の分割

Posted feedbacks - OCaml

Index

Feed

Other

Link

Pathtraq