製品のパーティション

Question

私は（私は正式な名前がわからない）「クラシック」パーティションで
我々は合計として正の整数の分解を検索し、「製品パーティション」についての情報を探しています：

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

私は製品として、すべての分解を見つけたい：

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

私は再帰的な解決策を持っているが、それは十分に効率的ではありません。
ご連絡ありがとうございます。 -------------------------

/// <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; 
} 

：

フィリップ
PS
は、ここで（C＃の）私の解決策であります---------------------（Jul、10）
ここにはさまざまな回答が掲載されていますが、私はまだパフォーマンスに関する問題があります。
素数が{2,3,5,7,11,13,17,19,23,29}で素数の最初のN個の要素の積に私のバージョンを適用すると、結果は次のようになります。

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... 

私は確かに良いです。
この機能が既に研究されていて、どこで情報を見つけることができたら、誰も私に答えませんでした。
インターネットで何度かの検索を無駄にしてみました...

もう一度お手伝いをしてください。
フィリップ

Answer 1

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

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

あなたが素数に因数アルゴリズムたら、コメントで述べたように：あなたがやりたいと思っている何

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?