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

post comment

Posted feedbacks - Lua

Lua です。

function split(n, m)
  if m == 0 then
    if n == 0 then coroutine.yield{} end
  else
    for i=n,0,-1 do
      for t in coroutine.wrap(function () split(n-i, m-1) end) do
        table.insert(t, 1, i) -- prepend
        coroutine.yield(t)
      end
    end
  end
end

function split_iter(n, m)
  return coroutine.wrap(function () split(n, m) end)
end

for i in split_iter(5, 3) do
  print(table.concat(i, ", "))
end

DouKaku?

自然数の分割

Posted feedbacks - Lua

Index

Feed

Other

Link

Pathtraq