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
我有一個遞歸解決方案，但它不是足夠有效的。
非常感謝您事先的任何信息。
菲利普
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;
}
------------------------- ---------------------（七月，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...
我相信有更好。
沒有人回答我，如果這個功能已經被研究，在那裏我能找到的信息。
我試圖在互聯網上進行多次搜索...
再次感謝您的幫助。
菲利普
你想要做什麼被稱爲「素分解」。歐幾里得算法會有幫助。 http://en.wikipedia.org/wiki/Euclidean_algorithm – Adam
我知道**素因子分解**和**歐幾里德算法**，但我不明白這與我的問題有何關係。我不想在素數因子中分解，我想找到所有產品是給定整數的子集（不包含1）。 – PhilippeC
爲什麼不告訴我們你到目前爲止的代碼，並解釋是什麼問題？ –