7

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!

Improve this question
17
  • 3
    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], [ab, c], [ac, b], [a, bc], [1, ab*c] and removing possible duplicates. Commented Feb 6, 2014 at 19:41
  • 7
    Are you aware that this is a NP-complete problem? Commented Feb 6, 2014 at 19:42
  • 2
    @epx Nope, it's definitely not a duplicate Commented Feb 6, 2014 at 19:45
  • 2
    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. :) Commented Feb 6, 2014 at 19:52
  • 1
    @malejpavouk He of course meant the Gödel prize Commented Feb 6, 2014 at 20:02

3 Answers 3

Reset to default
4

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,)
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

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!
@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 tuples. fixed now
3

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.

Improve this answer

1 Comment

Also, the answer you're pointing to, is this exact question :)
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)])
Improve this answer

2 Comments

Pretty cool although it is a lot slower than the algorithm posted by Claudiu. Thanks!
@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. =)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.