問題タブ [integer-partition]

整数分割テーブルがどのように機能するかを理解しようとしています。ただし、これまでのところ、作成できませんでした。

このクエリの問題点:

次のエラーが表示されます。

Error: PARTITION BY expression must be DATE(<timestamp_column>), a DATE column, or RANGE_BUCKET(<int64_column>, GENERATE_ARRAY(<int64_value>, <int64_value>, <int64_value>))

コードウォーズからの質問https://www.codewars.com/kata/52ec24228a515e620b0005ef/python

整数論と組み合わせ論では、整数分割とも呼ばれる正の整数 n の分割は、正の整数の和として n を記述する方法です。被加数の順序のみが異なる 2 つの合計は、同じパーティションと見なされます。順序が重要な場合、合計は合成になります。たとえば、4 は 5 つの異なる方法で分割できます。

数 n を指定して、n を分割できる方法の総数を返す関数 exp_sum(n) を作成します。例: exp_sum(4) = 5

再帰がアプローチする理由:

この特定の方法（このカタのトップソリューション）と比較して、実行に時間がかかりますか？

メモ化を使用しても、再帰アプローチは、上記のアプローチで 1000 ミリ秒かかるのに比べて、約 10000 ミリ秒でテスト ケースをほとんど通過できませんでした。

そして、上記の特定の方法がどのように機能するか、その背後にあるロジック、または私が読むことができる特定のアルゴリズムを使用しているかどうかを誰かが説明できますか?

このコードはどこかでオンラインで見つけたので、それがどのように機能するかを理解しようとしています。partitions() 関数に整数を指定すると、コードは繰り返し数を含まない個別のパーティションの数を返します (例: n = 5 -> 2 つのパーティション (3,2) & (4,1))。この再帰的なソリューションがこれをどのように管理しているかを正確に理解したいと思います。私はコードをいじり、再帰呼び出しを追跡してきましたが、それがどのように機能するのかまだよくわかりません。理解を助けてください。

次のコードでは、制限された整数パーティション (各番号は各パーティションで 1 回のみ発生する可能性があります) を各パーティションのk番号でカウントし1ますm。このコードは大量のキャッシュ値を生成するため、すぐにメモリ不足になります。

例：

sum := 15, k := 4, m:= 10期待される結果は6

次の制限付き整数パーティションがあります。

1,2,3,9、、、、、、1,2,4,8_ 1,2,5,7_ 1,3,4,7_ 1,3,5,7_2,3,4,6

キャッシュを回避/削減する公式はありますか? または、制限された整数部分をどのように数えることができますk and mか?