CODEWITHSUNDEEP
pythonalgorithmfactorizationdecomposition
Mr. T
Mr. T

Reputation: 12410

Create all possible factorisations from a prime factor list in Python

While I have seen posts about finding prime factors and divisors, I haven't found an answer to my question about factorisations in Python. I have a list of prime factors, i.e. for 24 it is [2,2,2,3]. I want from this list all possible factorisations, i.e. for 24 the output should be [[2,12], [3,8], [4,6], [2,2,6], [2,3,4], [2,2,2,3]]. I tried itertool approaches, but this created lots of duplicate answers and forgot others (like finding [2,3,4] but ignoring [4,6]).

I am specifically interested in an approach using the generated prime factor list. I have found a workaround with a recursive function.

def factors(n, n_list):                 
    for i in range(2, 1 + int(n ** .5)):
        if n % i == 0:
            n_list.append([i, n // i])
            if n // i not in primes:  #primes is a list containing prime numbers
                for items in factors(n // i, []):
                    n_list.append(sorted([i] + items))
    fac_list = [[n]]                  #[n] has to be added manually
    for facs in n_list:               #removes double entries     
        if facs not in fac_list:
            fac_list.append(facs)
    return fac_list

But this is time consuming for large n, since it has to look through all numbers, not just prime numbers. A combinatorics approach for a prime factor list should be much faster.

Edit: After looking through several resources, the best explanation of a good strategy is the highest rated answer here on SO. Concise and easy to implement in any language, one prefers. Case closed.

Upvotes: 3

Views: 416

Answers (1)

user448810
user448810

Reputation: 17866

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.

Upvotes: 3

Related Questions