# Algorithm to find ALL factorizations of an integer

Is there an algorithm to find ALL factorizations of an integer, preferably in Python/Java but any feedback is welcome.

I have an algorithm to calculate the prime factors. For instance [2,2,5] are the prime factors of 20.

```def prime_factorization(n):
primfac = []
d = 2
while d*d <= n:
while (n % d) == 0:
primfac.append(d)
n /= d
d += 1
if n > 1:
primfac.append(n)
return primfac
```

I also have an algorithm to compute all factors (prime and non-prime) of an algorithm. For instance, the factors of 20 are [1, 2, 4, 5, 10, 20].

```def factors(n):
a, r = 1, [1]
while a * a < n:
a += 1
if n % a: continue
b, f = 1, []
while n % a == 0:
n //= a
b *= a
f += [i * b for i in r]
r += f
if n > 1: r += [i * n for i in r]
return sorted(r)
```

What I'm searching for is an algorithm to return all factorizations (not factors) of a given integer. For the integer 20, the algorithm would produce the following:

```[1,20]
[2,10]
[4,5]
[2,2,5]
```

Thanks!

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
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,)
```

Just for fun:

```from itertools import combinations_with_replacement
from operator import mul

my_integer = 20
factorizations = {t for t in {list(t).remove(1) if 1 in t and len(t)>2 else t if len(t)>1 else None for combo in [combinations_with_replacement(factors(my_integer), n) for n in xrange(len(factors(my_integer)))] for t in combo if reduce(mul, t, 1) == my_integer} if t}

print factorizations
set([(4, 5), (2, 2, 5), (1, 20), (2, 10)])
```