Algorithm to find ALL factorizations of an integer

Question

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!

What have you tried? If you post your algorithm for all factors, I think you'll get more (and better) help. — Elliott Frisch, Feb 06 '14 at 19:38
I'll add the algorithm for all factors. I haven't coded anything to find the factorizations as I have no idea how to do it. — gieldops, Feb 06 '14 at 19:40
Whichever algorithm you use will be pretty much useless with moderately big numbers because the number of possible factorizations becomes really big really fast with the number of prime factors. Probably grows near `2^n` with `n` number of factors. — Bakuriu, Feb 06 '14 at 19:40
Once you have the prime factors (2, 2, 5) = (a,b,c), it is "only" a matter of finding all the combinations: [a, b, c], [a*b, c], [a*c, b], [a, b*c], [1, a*b*c] and removing possible duplicates. — assylias, Feb 06 '14 at 19:41
Possible duplicate of http://stackoverflow.com/questions/12421969/finding-all-divisors-of-a-number-optimization — epx, Feb 06 '14 at 19:42
Are you aware that this is a [NP-complete](http://en.wikipedia.org/wiki/NP-complete) problem? — Jakub Jirutka, Feb 06 '14 at 19:42
@epx Actually the question is not an exact duplicate, because it is *not* enough to get all divisors to obtain all "factorizations". Consider 100. you have both `[4, 25]` and `[4, 5, 5]`. The same divisor `4` appears in more than one factorization. The problem the OP is asking is *more* difficult then simply finding all divisors. — Bakuriu, Feb 06 '14 at 19:45
@Bakuriu I won't use it for big numbers. I'm going to try to implement assylias's method. I've thought of that but I thought it'd be a too naive solution. — gieldops, Feb 06 '14 at 19:48
Sorry, my comment about NP-complete is not exact correct (colleague of mine just pointed me). Complexity class of the integer factorization problem is still not known. It’s not P mostly likely, but probably it’s not even NP. However, the point is, that it’s damn hard problem. ;) If you invent polynomial algorithm for the integer factorization, just go for Nobel price and be careful, ’cause all security based on RSA will be lost. :) — Jakub Jirutka, Feb 06 '14 at 19:52
Again incorrect, you can't get Nobel prize for this... Because there is no Nobel prize in Math ;-)) — malejpavouk, Feb 06 '14 at 19:59
@malejpavouk Argh. See? Few days before my state exam and I have total mess in my head… :( So Gödel Prize or Abel Prize will be more likely. :) — Jakub Jirutka, Feb 06 '14 at 20:07
@JakubJirutka Also possible is the [Fields Medal](http://en.wikipedia.org/wiki/Fields_Medal). — Elliott Frisch, Feb 06 '14 at 20:34
possible duplicate of [How to find multiplicative partitions of any integer?](http://stackoverflow.com/questions/8558292/how-to-find-multiplicative-partitions-of-any-integer) — assylias, Feb 06 '14 at 22:40
@assylias Yes, I'm sorry. I didn't know it was called multiplicative partitions. — gieldops, Feb 07 '14 at 01:48

Claudiu · Accepted Answer · 2014-02-06T20:23:15.983

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

Well, it works perfectly for [2,3,5,7] but the first iteration of [2,2,5] returns (2,5) instead of (2,2,5). I'm trying to see where the mistake is. Thanks anyways! — gieldops, Feb 06 '14 at 20:21
@gieldl: oh my bad, I fixed it in my code but failed to edit that part. it's cause i was using `frozenset` instead of sorted `tuple`s. fixed now — Claudiu, Feb 06 '14 at 20:23

score 2 · Answer 2 · edited May 23 '17 at 11:58

2

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.

edited May 23 '17 at 11:58

Community

1
1

answered Feb 06 '14 at 20:11

user448810

17,381
4
34
59

1

Also, the answer you're pointing to, is this exact question :) – gieldops Feb 06 '14 at 20:14

That1Guy · Answer 3 · 2014-02-07T01:22:23.360

1

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

edited Feb 07 '14 at 01:22

answered Feb 06 '14 at 20:59

That1Guy

7,075
4
47
59

Pretty cool although it is a lot slower than the algorithm posted by Claudiu. Thanks! – gieldops Feb 07 '14 at 01:53
@gieldl Oh, yes. This is *very* inefficient. I only posted the answer as a fun one-liner to show that it *could* (not should) be done. =) – That1Guy Feb 07 '14 at 02:09

Algorithm to find ALL factorizations of an integer

3 Answers3