How to generate all multiplicative partitions of a number if I have a list of primes/exponents?
algorithm, number-theory, python
Solution
Your problem can be condensed into finding all of the partitions of a set, as each factor (prime and composite) can be represented as the product of the elements of a subset that makes up your partition.
I would represent the factors of your number as a list `[2, 2, 2, 3]` (well, a set). Here are some possible partitions of this list:
- `[2] + [2, 2, 3]`
- `[2, 2] + [2, 3]`
- `[2] + [2] + [2, 3]`
- `[3] + [2] + [2, 2]`
- ...
If you multiply together each element of each subset, you will get a factor of the original number:
- `2 * 12`
- `4 * 6`
- `2 * 2 * 6`
- `3 * 2 * 4`
You might have to add in a special case for `1 * n`.
Here's a relevant question: How can I maximally partition a set?
And another relevant link: Generating the Partitions of a Set
Problem
For instance, the number 24 has prime factorization 2^3*3^1, and can be written in the following ways ``` 1*24 2*12 2*2*6 2*3*4 2*2*2*3 3*8 4*6 ``` I may have missed one but you get the idea. I tried looking into the other thread How to find multiplicative partitions of any integer? but couldn't understand the answers in all honesty. I don't need anyone to write code for me but rather I could really use some help creating an efficient algorithm for this (probably something recursive?). I am coding in Python.