7

たとえば、24 の素因数分解は 2^3*3^1 であり、次のように記述できます。

1*24
2*12
2*2*6
2*3*4
2*2*2*3
3*8
4*6

私は1つ見逃したかもしれませんが、あなたはアイデアを得る.

他のスレッドを調べてみましたHow to find multiplicative partitions of any integer? しかし、正直なところ、答えを理解できませんでした。

誰かにコードを書いてもらう必要はありませんが、効率的なアルゴリズムを作成するための助けを借りることができます (おそらく再帰的なものでしょうか?)。

私はPythonでコーディングしています。

4

1 に答える 1

5

各因子 (素数と合成) は、パーティションを構成するサブセットの要素の積として表すことができるため、問題はset のすべてのパーティションを見つけることに凝縮できます。

あなたの数の要因をリスト[2, 2, 2, 3](まあ、セット)として表します。このリストのいくつかの可能なパーティションを次に示します。

  • [2] + [2, 2, 3]
  • [2, 2] + [2, 3]
  • [2] + [2] + [2, 3]
  • [3] + [2] + [2, 2]
  • ...

各サブセットの各要素を掛け合わせると、元の数の因数が得られます。

  • 2 * 12
  • 4 * 6
  • 2 * 2 * 6
  • 3 * 2 * 4

の特別なケースを追加する必要がある場合があり1 * nます。

関連する質問は次のとおりです。セットを最大限に分割するにはどうすればよいですか?

および別の関連リンク:セットのパーティションの生成

于 2012-11-15T02:24:53.663 に答える