title: Generating product partitions of a number
body: <p>While messing around with some algorithmic challenges, I've stumbled upon a problem the required me to get all possible partitions of an integer into a product.</p>
  
  <p>Now, the one straight-dumb-forward way to do it that I could think of is, given the number's prime factorization, to lump them all into a list, repeating each necessary amount of times to represent it's power in the factorization, and then to enumerate all partitions over that list.</p>
  
  <p>Obviously, while this works satisfactory if all factor powers are 1's, but gross amounts of redundant solutions if factors' powers are greater than one.</p>
  
  <pre class="lang-py prettyprint-override"><code># List partitions, turn them into product partitions
  # by multiplying the stuff in each subset and
  # then remove identical ones and compare the results
  def check_redundancy(s):
      p = list(partitions(s))
      pp = map(lambda x: tuple(sorted(map(prod, x))), p)
      pp = list(pp)
      print(f'Total partitions: {len(pp)}')
      ps = set(pp)
      print(f'Distinct product partitions: {len(ps)}')
  </code></pre>
  
  <p>Results are quite disgruntling in terms of unnecessary work done:</p>
  
  <pre class="lang-none prettyprint-override"><code>&gt;&gt;&gt; check_redundancy([2,2,3,3])
  Total partitions: 15
  Distinct product partitions: 9
  &gt;&gt;&gt; check_redundancy([2,2,2,2,2,3])
  Total partitions: 203
  Distinct product partitions: 19
  &gt;&gt;&gt; check_redundancy([2,2,2,2,2,2,3,3,3])
  Total partitions: 21147
  Distinct product partitions: 162
  &gt;&gt;&gt; check_redundancy([2,2,2,2,2,2,2,2,3,3,3])
  Total partitions: 678570
  Distinct product partitions: 401
  </code></pre>
  
  <p>So it's easily obvious that it gets real ugly performance-wise even around thousands (last example is actually just 6912 if you multiply it all). I've managed to get around the case of prime powers, since you only need to get all the integer partitions of the power to get all distinct products, but what has to be done for cases with two or more factors does, unfortunately, elude me so far.</p>
  
  <p>Any ideas for an algo that doesn't go around generating all the rendundant cases would be greatly appreciated!</p>