CODEWITHSUNDEEP
algorithmpython-2.7
Indranil Ghosh
Indranil Ghosh

Reputation: 31

List of all possible permutations of factors of a number

I am trying to find all the possible factorizations of a number provided in Python.

For example: 1)given n=12, the output will be, f(n)=[[2,2,3],[4,3],[6,2],[12]]

2) given n=24, the output will be,f(n)=[2,2,2,3],[2,2,6],[2,12],[4,6],[8,3],[24]]

Here is my code:

def p(a):
    k=1
    m=1
    n=[]
    for i in range (len(a)):
        for j in range(0,i+1):
            k*=a[j]
        for l in range(i+1,len(a)):
            m*=a[l]
        n+=[[k,m],]
        k=1
        m=1
    return n

def f(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 p(primfac)

But my code returns following values:

1) For n=12,The output is ,

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

2)1) For n=24,The output is ,

[[2, 12], [4, 6], [8, 3], [24, 1]]

What can I do for getting relevant results?

Upvotes: 0

Views: 664

Answers (1)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

I don't know python, so can't help you with the code, but here in an explanation I provided for a related question (a bit of Java code as well, if you can read Java).

  1. get your number factored with multiplicity - this is with high probability the most expensive step O(sqrt(N)) - you can stop here if this is al that you want

  2. build you sets of {1, pi1, pi1, ..., pimi} - pi being a prime factor with multiplicity of mi

  3. perform a Cartesian product between these sets and you'll get all the divisors of your number - you'll spend longer time here only for numbers with many distinct factors (and multiplicities) - e.g 210 x 3 8 x 54 x 73 will have 1980 divisors.

Now, each divisor d resulted from the above will come with it's pair (N/d) so if you want distinct factorisation irrespective of the order, you''l need to sort them and eliminate the duplicates.

Upvotes: 1

Related Questions