3

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.

Mr. T
  • 11,960
  • 10
  • 32
  • 54
  • Thanks for formatting my first post, jmd_dk. I took notice of the changes and will try to remember these rules. Is there a "blockshift to the right/left" command for code for proper indentation or do you have to add manually 4 spaces to each line? – Mr. T Nov 07 '17 at 08:49
  • Beginner's mistake - just use the `{}` button to format your code. – Mr. T Dec 08 '17 at 15:31

1 Answers1

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.

user448810
  • 17,381
  • 4
  • 34
  • 59
  • Much appreciated. "Multiplicative partition". No wonder, I didn't find the answer without the right keyword. – Mr. T Nov 07 '17 at 08:36