# 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!

## Answers

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

Your task is to determine the multiplicative partition of a number. Google should point you where you need to go. Stack Overflow already has an answer.

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)])