Wie kann ich alle multiplikativen Partitionen einer Zahl generieren, wenn ich eine Liste von Primzahlen/Exponenten habe?

Question

Die Zahl 24 hat zum Beispiel die Primfaktorzerlegung 2^3*3^1 und kann auf folgende Weise geschrieben werden

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

Vielleicht habe ich eine übersehen, aber Sie haben die Idee.

Ich habe versucht, in den anderen Thread zu schauen Wie findet man multiplikative Partitionen einer beliebigen ganzen Zahl? aber ehrlich gesagt konnte ich die Antworten nicht verstehen.

Ich brauche niemanden, der den Code für mich schreibt, aber ich könnte wirklich Hilfe gebrauchen, um einen effizienten Algorithmus dafür zu entwickeln (wahrscheinlich etwas Rekursives?).

Ich programmiere in Python.

Answer 1

Ihr Problem lässt sich dahingehend zusammenfassen, dass Sie alle Partitionen einer Menge da jeder Faktor (Primzahl und zusammengesetzte Zahl) als Produkt der Elemente einer Teilmenge dargestellt werden kann, aus der Ihre Partition besteht.

Ich würde die Faktoren Ihrer Zahl als eine Liste darstellen [2, 2, 2, 3] (na ja, ein Satz). Hier sind einige mögliche Unterteilungen dieser Liste:

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

Multipliziert man jedes Element jeder Teilmenge miteinander, so erhält man einen Faktor der ursprünglichen Zahl:

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

Möglicherweise müssen Sie einen Sonderfall hinzufügen für 1 * n .

Das ist eine wichtige Frage: Wie kann ich eine Menge maximal partitionieren?

Und ein weiterer relevanter Link: Generierung der Partitionen einer Menge