問題タブ [integer-partition]

これを行うための私のコードは次のとおりです。文字列表現では機能しますが、文字列表現では機能しませんArrayList<ArrayList<Integer>>。

私がtemp1で面白いビジネスをしている理由は、マスターに一時を追加すると、前の要素が変更されるためです（マスター内のすべての要素は同じ場所を指す参照になります）。コピー+クリア。

文字列は機能します。なぜそうではないのArrayList<ArrayList<Integer>>ですか？そして、どうすればそれを修正できますか？

の出力ArrayList<ArrayList<Integer>>は次のとおりです。

合計数（コード内の変数n ）の組み合わせの数を検索します。例：

3 = 1 + 1 + 1 = 2 + 1 = 3=>ANSは3

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1=>ANSは7

次の例では、mは最大数であり、n合計です。目的は、mがいくつの（合計）組み合わせを持っているかを見つけることです。

なぜそうするのか知りたいだけですp(n, m) = p(n, m - 1) + p(n - m, m)か？

ここのコード：

感謝！

与えられた と の順列についてN、の番目の順列を辞書順にk見つける関数があります。また、順列 が与えられた場合、 のすべての順列の中から順列の辞書式インデックスを見つける関数があります。これを行うには、この回答で提案されている「階乗分解」を使用しました。kNpermN

の整数パーティションに対して同じことをしたいと思いますN。たとえばN=7、インデックス (左) とパーティション (右) の間を行き来できるようにしたい:

私はいくつかのことを試しました。私が思いついた最高のものは

これにより、次のようになります。

これはうまくいきませんが、正しい軌道に乗っているようです。これを思いついたのは、数字を下に移動する必要がある回数をカウントするためです ( 6,3,2goes toのように6,3,1,1)。ただし、物事を再結合する必要がある場合を説明する方法がわからないため、修正方法がわかりません（ のよう6,3,1,1に6,2,2）。

整数 n の分割は、n を正の整数の和として記述する方法です。為に

たとえば、n=7 の場合、パーティションは 1+1+5 です。すべてを見つけるプログラムが必要です

'r' 整数を使用した整数 'n' のパーティション。たとえば、n=7

使用するr=3整数は1+1+5、1+2+4、1+3+3、2+2+3です。

これは私がこれまでに持っているものです:

このプログラムの出力は次のとおりです。

「r」変数を使用できるようにコードを変更するにはどうすればよいですか?

編集：

明確でない場合、'r' 値はパーティションごとの整数の数を表します。したがって、上記の場合、r=2 の場合、パーティションには 2 つの整数のみを含めることができます。パーティションは 4+1 と 3+2 になります。「r」値はユーザーが入力する必要があります。

次のように、関係する要素の数 (M) によって数 (N) の可能なパーティションの 1 つを見つける必要があります。

呼び出し P(4, 2) に対して次の結果を返す関数 P(N, M) を作成する必要があります。

次のメソッドを作成しましたが、各パーティション間の行を分割する方法が見つかりませんでした:

コードをもう一度更新しました。現在、文字列を使用して要素を返し、期待どおりの結果を得ることができましたが、パーティションを返すために文字列を使用せずに解決策を見つけようとしているため、文字列分割を使用する必要はありません関数。

Partitions クラスを含む C++ ライブラリを構築しています。活用 (以下で説明) を適切に実装しようとしていますが、機能させることができません。

私のクラスメンバーは次のとおりです。

例として、整数パーティション[5,4,4,1]には

分割が の場合、[m_1,m_2,...,m_k]共役は[n_1,n_2,...,n_l]

たとえば、 の共役は[5,4,4,1]です[4,3,3,3,1]。これを確認する別の方法は、パーティションを単位正方形の行として描画することです。ここで、行の正方形の数iは ですm_i。列の高さを読み取ると、共役が得られます。同じ例で、写真は

m_i = _parts[i-1]およびとしてプログラミング構文に変換された数学k = _length。共役の壊れた実装を次に示します。

これはほとんどの場合うまくいきますが、まだ必要なパーティションの一部を上書きすることがあります。の新しいインスタンスを作成せずに、その場で活用を行う賢い方法を探していますPartition。

活用を考えるもう 1 つの方法は、活用が次のシーケンスであることを認識することです。

このアイデアを使用して、正しい答えを与える次の実装があります。

ただし、回避しようとしている別の標準ベクトルを使用しています。

Evgeny Kluev の回答 (以下で承認) に沿って、機能する最終的なコードを次に示します (詳細については、彼の回答を参照してください)。

ボードゲームの確率解析プログラムを開発しています。アルゴリズム*の一部として、数字のパーティションの可能な順列（およびいくつかのパディング）を計算する必要があります。これにより、すべてのパーティションコンポーネントが、順列の合計長（桁数）から値を引いた値よりも低い位置を占めることができなくなりますコンポーネントの。

(ただし、分割される数が 8 を超えることはほとんどなく、順列の長さが 7 を超えることはありません。)

たとえば、パーティションが 4 の "211" で、パディングが 2、つまり長さが 5 の場合の順列を見つけたいとします。

これは {2,1,1,0,0} のような配列として表されます

2 が 0 インデックスにある場合は 6 つの順列 (4! / 2! 2!) があり、2 が占めることができるインデックスは 4 つあり (2 を最後のインデックスに配置することはできません)、この場合全体で 24 の順列があります ( 1 は任意のインデックスを占めることができます)。

入力 "21100" の出力:

21100、21010、21001、20110、20101、20011

02110、02101、02011、12100、12010、12001

00211、10210、11200、10201、01210、01201

10021、01021、00121、11020、10120 01120

これは単純に、「21100」から 2 が 4 番目のインデックスにあるものを差し引いたすべての順列のセットであることに注意してください。これは比較的単純なケースです。

この問題は、n 個の異なる順列グループの組み合わせとして説明できます。上記のケースは、x=1 n=4 の順列と x=2 n=5 の順列の組み合わせとして表現できるため、x は値のカウント、n は n です。 「スペース」カウントです。

私の困難は、すべての可能性を計算で取得できる方法を定式化することであり、アドバイスをいただければ幸いです。-私の質問で用語が混乱していることをお許しください。

*アルゴリズムは次の質問に答えます。

k回攻撃されるnユニットのセットがあります。各攻撃にはpの確率で失敗し、q (1 - p ) の確率でセットからランダムなユニットにダメージを与えます。2 度目のダメージを受けたユニットは破壊され、セットから取り除かれます。

攻撃後、無傷のユニットがx個、損傷したユニットがy個、破壊されたユニットがz個存在する確率は ?

誰かがこの問題へのより直接的なアプローチを知っているなら、私に知らせてください。