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

ありがちな再帰で。

def f(n, m):
  f0 = lambda n, m: [[i] + a for i in range(n, -1, -1) for a in f0(n-i, m-1)] if m > 1 else [[n]]
  for a in f0(n, m):
    for i in a:
      print '%d,' % i,
    print

f(5, 3)

Python で素直に書くとこうですかね。ところで、n >= m の条件って必要ないことないですか？n, m が整数なら n >= 0, m > 0 で十分なような。

import sys

def sum_perms(n, m):
    if m == 1:
        yield (n, )
    else:
        for i in reversed(xrange(n + 1)):
            for tail in sum_perms(n - i, m - 1):
                yield (i,) + tail

def main(args):
    if len(args) == 2:
        n, m = map(int, args)
    else:
        n, m = 5, 3

    for t in sum_perms(n, m):
        print t

if __name__ == '__main__':
    main(sys.argv[1:])

DouKaku?

自然数の分割

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq