An algorithm for finding ALL factorizations of an integer

Question

Is there an algorithm for finding ALL integer factorizations, preferably in Python / Java, but any feedback is appreciated.

I have an algorithm for calculating simple factors. For example, [2,2,5]are the main factors 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 for calculating all the factors (simple and not simple) of the algorithm. For example, the odds 20are equal [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)

I am looking for an algorithm to return all factorizations (not factors) of a given integer. For an integer, the 20algorithm will do the following:

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

Thanks!

Answer 1

. , , .

, n=1 len(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

:

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

:

for factorization in generate_all_factorizations([2, 2, 5]):
    print factorization
print "----"
for factorization in generate_all_factorizations([2, 3, 5, 7]):
    print factorization

:

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

Answer 2

- . Google , . " .

Answer 3

:

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