7

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.

Community
  • 1
  • 1
John Smith
  • 11,678
  • 17
  • 46
  • 51
  • 1
    Why on earth are there two votes to close? Can those who voted care to explain? – John Smith Nov 15 '12 at 02:07
  • You can boil your problem down to finding all of the possible partitions of a list. – Blender Nov 15 '12 at 02:08
  • @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? – John Smith Nov 15 '12 at 02:10

1 Answers1

5

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

Community
  • 1
  • 1
Blender
  • 289,723
  • 53
  • 439
  • 496
  • Does this require not only finding list partitions, but all permutations of partitions too? – John Smith Nov 15 '12 at 02:49
  • 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). – Blender Nov 15 '12 at 02:54
  • 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? – John Smith Nov 15 '12 at 02:57
  • @JohnSmith: What do the numbers in the output represent? – Blender Nov 15 '12 at 02:58
  • 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 – John Smith Nov 15 '12 at 02:59
  • @JohnSmith: That should work. I just realized that you can't have a set of sets in Python, which'll make things somewhat tricky. – Blender Nov 15 '12 at 03:04
  • 1
    @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])])` – Blender Nov 15 '12 at 03:07