Product partitions

Question

I am looking for information about "Product Partitions" (I don't know the official name)
In the "classic" partition we search the decompositions of a positive integer as sums:

Partition(5)   
         5  
       1 4  
       2 3  
     1 1 3  
     1 2 2  
   1 1 1 2  
 1 1 1 1 1

I want to find all the decompositions as products:

ProductPartition(36)  
      36  
    2 18  
    3 12  
    4 9  
     6 6  
   2 2 9  
   2 3 6  
   3 3 4  
 2 2 3 3

I have a recursive solution, but it is not efficient enough.
Thank you very much in advance for any information.

Philippe
PS
Here is my solution (C#):

/// <summary>
/// Products Partition 
/// ProductPartition(24) = (24)(2 12)(3 8)(4 6)(2 2 6)(2 3 4)(2 2 2 3)
/// </summary>
/// <param name="N"></param>
/// <returns></returns>
private List<List<long>> ProductPartition(long N)
{
    List<List<long>> result = new List<List<long>>();
    if (N == 1)
    {
        return result;
    }
    if (ToolsBox.IsPrime(N))
    {
        result.Add(new List<long>() { N });
        return result;
    }

    long[] D = ToolsBox.Divisors(N); // All divisors of N
    result.Add(new List<long>() { N });
    for (int i = 0; i < D.Length - 1; i++)
    {
        long R = N / D[i];
        foreach (List<long> item in ProductPartition(D[i]))
        {
            List<long> list = new List<long>(item);
            list.Add(R);
            list.Sort();
            result.Add(list);
        }
    }

    // Unfortunatly, there are duplicates
    result = L.Unique(result, Comparer).ToList();
    return result;
}

---------------------------------------------- (Jul, 10)
In spite of the various answers posted here, I'm still stuck with performance issues.
If primes is { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }, and I apply my version on the product of the first N elements of primes, here the result I get:

 N  ProductPartition    ms
 1  Count: 1    CPU:7
 2  Count: 2    CPU:10
 3  Count: 5    CPU:1
 4  Count: 15   CPU:6
 5  Count: 52   CPU:50
 6  Count: 203  CPU:478
 7  Count: 877  CPU:7372
 8  Count: 4140 CPU:56311
 9  Abort after several minutes...

I am sure there is better.
Nobody answered me if this function has already been studied and where I could find informations.
I tried several searches on the Internet in vain ...

Thanks again for your help.
Philippe

What you are wanting to do is called 'Prime Factorization'. The Euclidean Algorithm will be of help. http://en.wikipedia.org/wiki/Euclidean_algorithm — Adam, Jun 27 '11 at 15:24
I know **prime factorization** and **Euclidean algorithm**, but I don't see how this relates to my question. I am not trying to decompose in prime factors, I want to find all the subsets (not containing 1) whose products are a given integer. — PhilippeC, Jun 27 '11 at 16:20
Why don't you show us the code you have so far, and explain what the problem is? — Gareth Rees, Jun 27 '11 at 21:26
Once you have the prime factorization generating these sets is almost trivial (with a caveat about repeating factors) — zienkikk, Jun 29 '11 at 03:58

score 0 · Answer 1 · edited May 23 '17 at 11:48

0

http://en.wikipedia.org/wiki/Integer_factorization

http://en.wikipedia.org/wiki/Integer_factorization#General-purpose

As mentioned in the comments, once you have an algorithm which factors into primes:

def allFactors(num):
    primeFactors = algorithm(num)
    return (product(subset) for subset in combinations(primeFactors))

How to get all possible combinations of a list’s elements?

edited May 23 '17 at 11:48

Community

1
1

answered Jul 01 '11 at 00:41

ninjagecko

88,546
24
137
145

Product partitions

1 Answers1