Je cherche des informations sur les « partitions produit » (je ne sais pas le nom officiel)
Dans la partition « classique » on recherche les décompositions d'un entier positif sommes:partitions du produit
Partition(5)
5
1 4
2 3
1 1 3
1 2 2
1 1 1 2
1 1 1 1 1
Je veux trouver tous les décompositions en tant que produits:
ProductPartition(36)
36
2 18
3 12
4 9
6 6
2 2 9
2 3 6
3 3 4
2 2 3 3
J'ai une solution récursive, mais il ne suffit pas efficace.
Merci beaucoup d'avance pour toute information.
Philippe
PS
Voici ma 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)
En dépit des différentes réponses affichées ici, je suis toujours coincé avec des problèmes de performance.
Si nombres premiers sont {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} et j'applique ma version sur le produit des N premiers éléments de nombres premiers, voici le résultat obtenu:
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...
Je suis sûr qu'il y a mieux.
Personne ne m'a répondu si cette fonction a déjà été étudiée et où je pourrais trouver des informations.
J'ai essayé plusieurs recherches sur Internet en vain ...
Merci encore pour votre aide.
Philippe
ce que vous voulez faire est appelé «Factorisation principale». L'algorithme euclidien sera utile. http://en.wikipedia.org/wiki/Euclidean_algorithm – Adam
Je connais ** la factorisation en nombres premiers ** et ** l'algorithme euclidien **, mais je ne vois pas comment cela se rapporte à ma question. Je ne cherche pas à décomposer en facteurs premiers, je veux trouver tous les sous-ensembles (ne contenant pas 1) dont les produits sont un entier donné. – PhilippeC
Pourquoi ne nous montrez-vous pas le code que vous avez déjà, et expliquez-vous quel est le problème? –