Here's a pretty inefficient way to do it. It generates a lot of duplicates and then filters them out before returning them.
The idea is you pick from n=1
to len(factors)
inclusive factors to multiply, and then you recur into the unused factors.
import itertools
def mult(fs):
res = 1
for f in fs:
res *= f
return res
def _generate_all_factorizations(factors):
if len(factors) <= 1:
yield factors
return
for factors_in_mult in xrange(1, len(factors)+1):
for which_is in itertools.combinations(range(len(factors)), factors_in_mult):
this_mult = mult(factors[i] for i in which_is)
rest = [factors[i] for i in xrange(len(factors)) if i not in which_is]
for remaining in _generate_all_factorizations(rest):
yield [this_mult] + remaining
I added a function to remove duplicates and return them nicely sorted:
def generate_all_factorizations(factors):
seen = set()
res = []
for f in _generate_all_factorizations(factors):
f = tuple(sorted(f))
if f in seen:
continue
seen.add(f)
yield f
Now just feed it your prime factorization:
for factorization in generate_all_factorizations([2, 2, 5]):
print factorization
print "----"
for factorization in generate_all_factorizations([2, 3, 5, 7]):
print factorization
Result:
(2, 2, 5)
(2, 10)
(4, 5)
(20,)
----
(2, 3, 5, 7)
(2, 3, 35)
(2, 5, 21)
(2, 7, 15)
(2, 105)
(3, 5, 14)
(3, 7, 10)
(3, 70)
(5, 6, 7)
(5, 42)
(7, 30)
(6, 35)
(10, 21)
(14, 15)
(210,)