指定された整数のすべてのパーティションを生成する必要があります。
私は、ジェローム・ケレハーによるこのアルゴリズムを見つけました。これは、最も効率的なアルゴリズムであると言われています。
def accelAsc(n):
a = [0 for i in range(n + 1)]
k = 1
a[0] = 0
y = n - 1
while k != 0:
x = a[k - 1] + 1
k -= 1
while 2*x <= y:
a[k] = x
y -= x
k += 1
l = k + 1
while x <= y:
a[k] = x
a[l] = y
yield a[:k + 2]
x += 1
y -= 1
a[k] = x + y
y = x + y - 1
yield a[:k + 1]
参照: http: //homepages.ed.ac.uk/jkellehe/partitions.php
ちなみに、あまり効率的ではありません。このような入力の場合40
、出力を提供する前に、システム全体が数秒間フリーズします。
再帰的なアルゴリズムだとしたら、キャッシュ機能などで装飾して効率を上げようと思いますが、そういうわけではどうしたらいいのかわかりません。
このアルゴリズムを高速化する方法についていくつか提案がありますか?または、別のアプローチ、または別のアプローチを最初から作成するための別のアプローチを提案できますか?