問題タブ [integer-partition]

k 個の部分で n のすべてのパーティションを列挙しようとしています。

したがって、p(5,3) の場合、k = 3 => (3,1,1)、(2,2,1) の 2 つのパーティションが得られます。

stackoverflow を検索して調べた結果、次のことがわかりました。

^^^^これは私が望む形です。

そのままで、k 個の部分の合計を見つけるのは簡単です。p(n-1, k-1) + p(nk,k) を返します。私の場合、[(3,1,1), (2,2,1)] のように各要素をリストする必要があります。

私の主な問題は、これらのパーティションを再帰的に「構築」することです。これにどのように取り組みますか？

編集

基本ケース k = 1 を取得する場合は、+ 1、k-1 回を追加します。(4,1) 次に (4,1,1)

基本ケース k = n の場合は、分割して各部分に 1 つを削除します。

そのように：（3,3）次に（3,3,3）そして（2,2,2）

基本ケース k < n の場合、何もありません

基本的に、私の問題は、ベースケースからトップまでのものを「積み重ね」、完全なリストを取得することです p(6,3) = [(2,2,2), (4,1,1), (3,2 、1)]

これは宿題の質問であり、動的プログラミングのアプローチを使用して解決する必要があります。

私がこれまでにできたことは、次のとおりです。

f(x) が、x が記述できる回数を表すとします。

次に、f(x) = f(x - 1) + 1 です。f(5) = f(4) + 1 (5 = 4 + 1)

しかし、私はこれが正しいアプローチだとは思いません。誰でも助けたいですか？

問題が実際に何であるかの例:

書ける方法の数 4:

2 つの整数を と とし、正の数を合計して を得る方法がいくつあるかを返すメソッドを作成する必要nがありmます。たとえば、このようなメソッド呼び出しは、可能な方法が 3 つあるため、3 を返す必要があります。それらは、、およびです。ちなみに、は と同じなので、このメソッドはそれらを 2 つの異なるバリエーションとして数えるべきではありません。誰も問題の解決策を知っていますか?mnpartition(6, 2)5 + 14 + 23 + 34 + 22 + 4

更新:nおよびmは 150 以下です。

整数パーティションの次のコードを検討してください。

p(7,3) を例にとると、関数が p(7,0) & p(4,3) になった後はどうなりますか?

以前のパーティションを使用すると速度が向上するという考えで、整数を繰り返し分割し、以前の結果を使用して数値を完全に分割するコードに取り組んできました。これまでのところ、整数を再帰的に分割するよりもパフォーマンスが 22 倍遅くなり、すぐにメモリ不足になるため、より大きな数をテストできませんでした。誰かがコードの最適化を手伝ってくれるなら、私はその助けに感謝します.

ベクトルsを次のように考えます。

s固定長が与えられmたので、マトリックスの各行の合計が(ブルート フォース アプローチを除く)になるように、長さのすべての可能な順列のマトリックスが必要です。m1

たとえば、m=4(つまり、列の数) の場合、目的の行列は次のようになります。

各正の整数 n には 2^(n−1) 個の異なる構成があります。リストにある特定の番号のみを持つ構成の番号が必要な場合：

例えば4の合成は

しかし、1と2しかない4の構成の数が必要な場合、異なる構成のNUMBERをどのように計算できますか?

編集: ここでは数字を計算する Haskell コードですが、数字 70 の暗記を追加しても時間がかかりすぎると思います

この質問は、私が数ヶ月前に持っていた質問に似ています: Generating a numpy array with all numbers of numbers that sum to less than a given number . その質問では、各要素に特定の最大値があることを考えると、最大でも定数になるすべての数値を生成したいと考えていました。

今回は、合計すると正確にその定数になるすべての順列を計算したいと思います。これは、各要素が特定の最大値を持つ整数パーティションの一意の順列を計算することと見なすことができます。最終結果は、numpy 配列に格納する必要があります。

ジェネレーターを使用すると、ワンライナーで目的が達成されます。

与える

K=20と の場合、パフォーマンスが非常に遅くなりmaxRange = [20]*6ます。順列の数は 53130 と制限されていますが、既に 20 秒かかります。私の直感では、これには 1 秒もかからないはずです。

より高速なソリューションを利用できる人はいますか? これを説明するために以前の質問の解決策を変更するのに苦労していますK.

numbaの演算子を使用するソリューションは気にしません@jit...それらが現在持っているものよりも高速である限り!

前もって感謝します。

次のアルゴリズムが必要です。

• 指定されたターゲット合計nと指定された制限mが与えられます。これらは両方とも正の整数です。
• 被加数ができるだけ少ないターゲット合計nの整数分割を見つけたいと考えています。
• 各被加数は制限m以下でなければなりません。
• 上記の制約の範囲内で、被加数はできるだけ互いに近づける必要があります。つまり、nをできるだけ均等に分割する必要があります。

したがって、たとえば、ターゲットの合計がn  = 80 で、各加数が最大で m  = 30 でなければならない場合、少なくとも 3 つの加数が必要であり、最も偶数のパーティションは26 + 27 + 27です。

どうやってそれを計算しますか？