ボードゲームの確率解析プログラムを開発しています。アルゴリズム*の一部として、数字のパーティションの可能な順列（およびいくつかのパディング）を計算する必要があります。これにより、すべてのパーティションコンポーネントが、順列の合計長（桁数）から値を引いた値よりも低い位置を占めることができなくなりますコンポーネントの。
(ただし、分割される数が 8 を超えることはほとんどなく、順列の長さが 7 を超えることはありません。)
たとえば、パーティションが 4 の "211" で、パディングが 2、つまり長さが 5 の場合の順列を見つけたいとします。
0 1 2 3 4 (array indexes)
5 4 3 2 1 (maximum value of partition component that can be allocated to each index)
2 1 1 _ _ (the partition plus 2 empty indexes)
これは {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個存在する確率は ?
誰かがこの問題へのより直接的なアプローチを知っているなら、私に知らせてください。