Databases
StackOverflow2013
Postsdbo
POProduct partitions
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POProduct partitions
    primarykey
    data
    text
    <p>I am looking for information about "Product Partitions" (I don't know the official name)<br> In the "classic" partition we search the decompositions of a positive integer as sums: </p> <pre><code>Partition(5) 5 1 4 2 3 1 1 3 1 2 2 1 1 1 2 1 1 1 1 1 </code></pre> <p>I want to find all the decompositions as products: </p> <pre><code>ProductPartition(36) 36 2 18 3 12 4 9 6 6 2 2 9 2 3 6 3 3 4 2 2 3 3 </code></pre> <p>I have a recursive solution, but it is not efficient enough.<br> Thank you very much in advance for any information.</p> <p>Philippe<br> PS<br> Here is my solution (C#): </p> <pre><code>/// &lt;summary&gt; /// Products Partition /// ProductPartition(24) = (24)(2 12)(3 8)(4 6)(2 2 6)(2 3 4)(2 2 2 3) /// &lt;/summary&gt; /// &lt;param name="N"&gt;&lt;/param&gt; /// &lt;returns&gt;&lt;/returns&gt; private List&lt;List&lt;long&gt;&gt; ProductPartition(long N) { List&lt;List&lt;long&gt;&gt; result = new List&lt;List&lt;long&gt;&gt;(); if (N == 1) { return result; } if (ToolsBox.IsPrime(N)) { result.Add(new List&lt;long&gt;() { N }); return result; } long[] D = ToolsBox.Divisors(N); // All divisors of N result.Add(new List&lt;long&gt;() { N }); for (int i = 0; i &lt; D.Length - 1; i++) { long R = N / D[i]; foreach (List&lt;long&gt; item in ProductPartition(D[i])) { List&lt;long&gt; list = new List&lt;long&gt;(item); list.Add(R); list.Sort(); result.Add(list); } } // Unfortunatly, there are duplicates result = L.Unique(result, Comparer).ToList(); return result; } </code></pre> <p>---------------------------------------------- (Jul, 10)<br> In spite of the various answers posted here, I'm still stuck with performance issues.<br> 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: </p> <pre><code> 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... </code></pre> <p>I am sure there is better.<br> Nobody answered me if this function has already been studied and where I could find informations.<br> I tried several searches on the Internet in vain ... </p> <p>Thanks again for your help.<br> Philippe</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USChris Gerken
    1. USPhilippeC
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COWhat you are wanting to do is called 'Prime Factorization'. The Euclidean Algorithm will be of help. http://en.wikipedia.org/wiki/Euclidean_algorithm
      singulars
      1. POProduct partitions
      1. USAdam
    2. COI 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.
      singulars
      1. POProduct partitions
      1. USPhilippeC
    3. COWhy don't you show us the code you have so far, and explain what the problem is?
      singulars
      1. POProduct partitions
      1. USGareth Rees
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload