自然数の分割 in Pnuts 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 - Pnuts

たまには Pnuts などを

function sum_perms(n, m) {
    if (m == 1) {
        yield [n]
    }
    else if (n == 0) {
        yield new int[m]
    }
    else {
        for (i : n..0) {
            for (rest : sum_perms(n - i, m - 1)) {
                yield [i] + rest
            }
        }
    }
}

function main(args) {
    if (args.length == 2) {
        n, m = project(args, function(o) { int(o) })
    }
    else {
        n, m = [5, 3]
    }

    for (t : sum_perms(n, m)) {
        println(join(' ', t))
    }
}

main($args[1..])

DouKaku?

自然数の分割

Posted feedbacks - Pnuts

Index

Feed

Other

Link

Pathtraq