How to generate all multiplicative partitions of a number if I have a list of primes/exponents?

Question

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.

Firebrat

Why on earth are there two votes to close? Can those who voted care to explain? – Firebrat

You can boil your problem down to finding all of the possible partitions of a list. – Atticism

@Blender: I have a method for finding additive partitions of a number. Is this what you mean? If so, how does that relate to multiplicative partitions? – Firebrat

Answer 1

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

Atticism

Does this require not only finding list partitions, but all permutations of partitions too? – Firebrat

Nope, just partitions. My examples were a little lazy, sorry. A partition is just a collection of subsets that, when combined, form the original set. A subset is just a set of elements that's contained within the original set (not in any specific order). – Atticism

I have a generator that would yield, in the case of 24, which has four total nondistinct prime factors 2,2,2,3, of [1, 1, 1, 1] [1, 1, 2], [2, 2], [1, 3], [4] is this enough? Don't I have to swap all these around the prime factors every possible way? – Firebrat

@JohnSmith: What do the numbers in the output represent? – Atticism

Additive partitions of 4 (to represent the different ways of clustering the primes) so [4] might correspond to (2*2*2*3) and [1,3] might correspond to (2)*(2*2*3) etc – Firebrat

@JohnSmith: That should work. I just realized that you can't have a set of sets in Python, which'll make things somewhat tricky. – Atticism

@JohnSmith: Wait, no it won't. frozenset can be used for the inner sets instead: frozenset([frozenset([3]), frozenset([2, 1])]) == frozenset([frozenset([1, 2]), frozenset([3])]) – Atticism