0

「プロダクト パーティション」についての情報を探しています (正式な名前はわかりません)
。「クラシック」パーティションでは、正の整数の分解を合計として検索します。 

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

再帰的な解決策がありますが、十分に効率的ではありません。
情報をお寄せいただきありがとうございます。

Philippe
PS
これが私の解決策です(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;
}

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

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

ご協力いただきありがとうございます。
フィリップ

4

1 に答える 1