数を分割する方法を列挙したリストを返す関数を作りたい

前提・実現したいこと

言葉で表すのは難しいのですが、以下のような関数を作成しています。
どのようにこの関数を実装すればいいでしょうか？
お手数ですが、ご回答お願いします。

ソースコード

print(hoge_function(1))  # => [[1]]
print(hoge_function(2))  # => [[2], [1, 1]]
print(hoge_function(3))  # => [[3], [1, 2], [2, 1], [1, 1, 1]]
print(hoge_function(4))  # => [[4], [1, 3], [2, 2], [3, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 1, 1]]
.
.
.

条件

返り値はリスト
その各要素もリスト
その要素を全て足すと、引数の値になる

環境

python 3.7.4

行動規範の内容に同意します

回答2件

命題は「自然数Nが与えられた時に、足してNになる自然数を列挙する」と解釈して作ってみました。

python
1# 自然数Nが与えられた時に、足してNになる自然数を列挙する．
2# 考え方：NをN進数を構成する自然数のリストを作成し、そのリストの和がNなら求めるものとする。
3#         それをN-1、N-2、・・・と繰り返す．
4import pprint
5
6def n_base_comb(n_base, num): # numをn_base進のリストで返す
7    ret_list = []
8    q, m = divmod(num, n_base)
9    ret_list.append(m)
10    while q > 0:
11        q, m = divmod(q, n_base)
12        ret_list.append(m)
13    return list(reversed(ret_list))
14
15def n_base_list_gen(N, n_base, n_comb): # n_combは組合せ数
16    num_max = n_base ** n_comb
17    i = 0
18    ret = []
19    while i < num_max:
20        n_base_comb_list = n_base_comb(n_base, i)
21        if  len(n_base_comb_list) != n_comb or 0 in n_base_comb_list:
22            i += 1
23            continue
24        if sum(n_base_comb_list) == N:
25            ret.append(n_base_comb_list)
26        i += 1
27    return ret
28
29def hoge_function(N):
30    assert N > 0, "N は自然数のこと．"
31    ret_list = [[N]]
32    n_comb = 2
33    for n in range(N, 2, -1):
34        n_base_list = n_base_list_gen(N, n, n_comb)
35        for el in n_base_list:
36            ret_list.append(el)
37        n_comb += 1
38    if N > 1:
39        ret_list.append([1]*N)
40    return ret_list
41
42def main():
43    pprint.pprint(hoge_function(1))
44    pprint.pprint(hoge_function(2))
45    pprint.pprint(hoge_function(3))
46    pprint.pprint(hoge_function(4))
47    pprint.pprint(hoge_function(5))
48    pprint.pprint(hoge_function(6))
49    return
50
51if __name__ == '__main__':
52    main()

result
1[[1]]
2[[2], [1, 1]]
3[[3], [1, 2], [2, 1], [1, 1, 1]]
4[[4], [1, 3], [2, 2], [3, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 1, 1]]
5[[5],
6 [1, 4],
7 [2, 3],
8 [3, 2],
9 [4, 1],
10 [1, 1, 3],
11 [1, 2, 2],
12 [1, 3, 1],
13 [2, 1, 2],
14 [2, 2, 1],
15 [3, 1, 1],
16 [1, 1, 1, 2],
17 [1, 1, 2, 1],
18 [1, 2, 1, 1],
19 [2, 1, 1, 1],
20 [1, 1, 1, 1, 1]]
21[[6],
22 [1, 5],
23 [2, 4],
24 [3, 3],
25 [4, 2],
26 [5, 1],
27 [1, 1, 4],
28 [1, 2, 3],
29 [1, 3, 2],
30 [1, 4, 1],
31 [2, 1, 3],
32 [2, 2, 2],
33 [2, 3, 1],
34 [3, 1, 2],
35 [3, 2, 1],
36 [4, 1, 1],
37 [1, 1, 1, 3],
38 [1, 1, 2, 2],
39 [1, 1, 3, 1],
40 [1, 2, 1, 2],
41 [1, 2, 2, 1],
42 [1, 3, 1, 1],
43 [2, 1, 1, 2],
44 [2, 1, 2, 1],
45 [2, 2, 1, 1],
46 [3, 1, 1, 1],
47 [1, 1, 1, 1, 2],
48 [1, 1, 1, 2, 1],
49 [1, 1, 2, 1, 1],
50 [1, 2, 1, 1, 1],
51 [2, 1, 1, 1, 1],
52 [1, 1, 1, 1, 1, 1]]

投稿2020/02/04 02:07

ikapy

総合スコア1167

python
1import itertools
2
3def hoge_function(x):
4    if x == 1 : return [[1]]
5    a = [ tuple( itertools.permutations( [y] + [1] * ( x - y ) ) ) for y in range ( 1, x ) ]
6    return [ x for x in set( itertools.chain.from_iterable( a ) ) ]