Décomposition d'un nombre en sommets

Cette calculatrice en ligne pour un nombre saisi entre 1 et 60 affiche toutes ses représentations sous forme de somme d'entiers positifs, ainsi que le nombre de ces représentations.

En mathématiques, la représentation d'un nombre sous la forme d'une somme d'entiers positifs est appelée partition d'un entier naturel n, la notation canonique de la partition énumérant les sommets par ordre non croissant. Une description de l'algorithme permettant de générer toutes les partitions peut être trouvée sous la calculatrice.

Partition d'un nombre naturel

Nombre naturel

Calculer

Nombre de combinaisons

 

Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Télécharger 

 Lien  sauvegarder  Widget

Le problème de la décomposition d'un nombre en ses sommets

La plupart des sources, que l'on peut facilement trouver en cherchant, donnent un algorithme récursif pour décomposer un nombre en sommands. Cette calculatrice, cependant, utilise un algorithme itératif pour des raisons techniques. La logique de l'algorithme est tirée d'un article sur Habre.

Comme la logique de l'algorithme est assez concise, je vais la donner dans son intégralité (avec quelques commentaires) :

Donné : le tableau initial sous forme d'unités est A (1,1,1,1,1,1,1,1,1,1).

La dimensionnalité du tableau correspond au nombre n dont on cherche tous les développements.

0) Si on obtient la somme, on arrête l'algorithme.

Comme l'auteur de l'article, je fais la somme des éléments du tableau, à la fin il ne doit rester qu'un élément d'indice 0, numériquement égal à n.

1) En parcourant le tableau de gauche à droite, rechercher dans le tableau A le premier élément minimum - x,
le dernier élément n'est pas pris en compte (il ne participe pas à la recherche de l'élément minimal).

Nous avons besoin à la fois de la valeur de l'élément et de sa position dans le tableau. C'est pourquoi je n'utilise pas les fonctions Javascript intégrées telles que min et findIndexOf, mais une seule itération à travers le tableau, en me souvenant à la fois de l'élément minimal actuel et de sa position, ainsi que de la somme jusqu'à l'élément minimal actuel inclus (la somme sera nécessaire plus loin).

2) Déplacer un élément de la fin (dernier élément) vers l'élément minimal trouvé x
(ce qui équivaut à augmenter x d'une unité et à diminuer le dernier élément d'une unité).

Ici, l'unité est ajoutée et la méthode d'épissage est utilisée.

3) Décomposer la somme de tous les éléments après l'élément modifié - x - en unités.

Ici, nous ajoutons des unités en utilisant la somme partielle calculée précédemment.

Le code Javascript de l'algorithme est donné ci-dessous (les divisions sont affichées sur la console) :
``javascript
function split(n) {
var temp = [] ;
for(var i = 0 ; i ＜ n ; ++i) temp.push(1) ;
while(temp[0] != n)
{
console.log(temp) ;
var min = temp[0] ;
var minindex = 0 ;
var sum = temp[0] ;
var tempsum = temp[0] ;
for(var j = 1 ; j ＜ temp.length - 1 ; ++j) {
tempsum += temp[j] ;
if (min ＞ temp[j]) {
min = temp[j] ;
minindex = j ;
sum = tempsum ;
}
}
temp[minindex] += 1 ;
sum += 1 ;
temp.splice(minindex+1) ;
for (var k = 0 ; k ＜ n - sum ; ++k) temp.push(1) ;
}
console.log([n]) ;
}

Il reste à ajouter que, comme dans tout autre problème combinatoire, le nombre de splits dépend exponentiellement du nombre _n_. S'il est de 42 pour 10, il est déjà de 204 226 pour 50, et de 190 569 292 pour 100. Cette calculatrice a une limite de 60, ce qui donne 966 467 décompositions et prend environ 12 secondes à compter sur mon ordinateur portable. À 100, le navigateur a manqué de mémoire et s'est arrêté. 

La dépendance du nombre de décompositions par rapport à _n_ est une séquence de nombres [[link:http://oeis.org/A000041|A000041]] dans l'Encyclopédie en ligne des séquences d'entiers et possède quelques propriétés intéressantes.