あなたが再帰的にこれを行うことができますが、（木のように）再帰的なデータ構造を処理するときに、あなた本当には、例えば、それを必要としない限り、それはPythonで再帰を避けるために、一般的にお勧めします。標準的なPython（別名CPython）の再帰は、tail callの削除を行うことができないため、あまり効率的ではありません。また、再帰制限（デフォルトでは1000レベルですが、ユーザーが変更できる）を適用します。
生成するシーケンスはweak compositions、ウィキペディアの記事では標準のitertools.combinations関数を使用して実装が簡単な簡単なアルゴリズムを示しています。
#!/usr/bin/env python3
''' Generate the compositions of num of a given width
Algorithm from
https://en.wikipedia.org/wiki/Composition_%28combinatorics%29#Number_of_compositions
Written by PM 2Ring 2016.11.11
'''
from itertools import combinations
def compositions(num, width):
m = num + width - 1
last = (m,)
first = (-1,)
for t in combinations(range(m), width - 1):
yield [v - u - 1 for u, v in zip(first + t, t + last)]
# test
for t in compositions(5, 4):
print(t)
print('- ' * 20)
for t in compositions(3, 3):
print(t)
出力
[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 0, 3, 2]
[0, 0, 4, 1]
[0, 0, 5, 0]
[0, 1, 0, 4]
[0, 1, 1, 3]
[0, 1, 2, 2]
[0, 1, 3, 1]
[0, 1, 4, 0]
[0, 2, 0, 3]
[0, 2, 1, 2]
[0, 2, 2, 1]
[0, 2, 3, 0]
[0, 3, 0, 2]
[0, 3, 1, 1]
[0, 3, 2, 0]
[0, 4, 0, 1]
[0, 4, 1, 0]
[0, 5, 0, 0]
[1, 0, 0, 4]
[1, 0, 1, 3]
[1, 0, 2, 2]
[1, 0, 3, 1]
[1, 0, 4, 0]
[1, 1, 0, 3]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3, 0]
[1, 2, 0, 2]
[1, 2, 1, 1]
[1, 2, 2, 0]
[1, 3, 0, 1]
[1, 3, 1, 0]
[1, 4, 0, 0]
[2, 0, 0, 3]
[2, 0, 1, 2]
[2, 0, 2, 1]
[2, 0, 3, 0]
[2, 1, 0, 2]
[2, 1, 1, 1]
[2, 1, 2, 0]
[2, 2, 0, 1]
[2, 2, 1, 0]
[2, 3, 0, 0]
[3, 0, 0, 2]
[3, 0, 1, 1]
[3, 0, 2, 0]
[3, 1, 0, 1]
[3, 1, 1, 0]
[3, 2, 0, 0]
[4, 0, 0, 1]
[4, 0, 1, 0]
[4, 1, 0, 0]
[5, 0, 0, 0]
- - - - - - - - - - - - - - - - - - - -
[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]
FWIW、上記のコードは、Python 3.6またはPythonの2.6上で実行されている、私の古い2GHzの32ビットマシン上で周りの1.6秒でcompositions(15, 8)の170544のシーケンスを生成することができます。 （タイミング情報は、Bash timeコマンドを使用して取得しました）。
FWIW、ここuser3736966によりthis answerから取られた再帰的なバージョンがあります。私はやや意外にも、この1つは、元のバージョンよりも少し速いです
def compositions(num, width, parent=[]):
if width > 1:
for i in range(num, -1, -1):
yield from compositions(i, width - 1, parent + [num - i])
else:
yield parent + [num]
をリストの代わりにタプルを使用するように、私のコードと同じ引数名を使用するように変更した、とPython 3と互換性があるようにcompositions(15, 8)の場合は約1.5秒でクロッキングします。
のPythonのバージョンがyield fromを理解していない場合は、これを行うことができます：単にrangeコール、すなわちfor i in range(num + 1):を逆に、降順で組成物を生成するには
def compositions(num, width, parent=[]):
if width > 1:
for i in range(num, -1, -1):
for t in compositions(i, width - 1, parent + [num - i]):
yield t
else:
yield parent + [num]
を。
最後に、読むことができない1行バージョンです。根っからのtinkererビーイング:)
def c(n, w, p=[]):
yield from(t for i in range(n,-1,-1)for t in c(i,w-1,p+[n-i]))if w-1 else[p+[n]]
、私はまだ別のバージョンを作るから自分自身を止めることができませんでした。 :)これは単に、元のバージョンとcombinationsのコードを組み合せたもので、itertoolsドキュメントにリストされています。もちろん、実際のitertools.combinationsはwritten in Cなので、ドキュメントに表示されているほぼ同等のPythonコードよりも速く実行されます。
def compositions(num, width):
r = width - 1
indices = list(range(r))
revrange = range(r-1, -1, -1)
first = [-1]
last = [num + r]
yield [0] * r + [num]
while True:
for i in revrange:
if indices[i] != i + num:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield [v - u - 1 for u, v in zip(first + indices, indices + last)]
このバージョンでは、compositions(15, 8)をやっでオリジナルよりも約50％遅い：それは私のマシン上で周りに2.3秒かかります。
なぜあなたはitertoolsがあなたのRAMをいっぱいにすると思いますか？これは、怠惰なイテレータになるように特別に設計されています。すべての順列を一度に作成するわけではありません。 – jonrsharpe
@jonrsharpe実際に私たちはそれを試しました。それは私たち自身のソリューションよりも長くかかりました。 –
それはあなたのRAMをいっぱいにすることとは異なりますが... – jonrsharpe