Lister toutes les compositions ordonnées d'un entier

Une composition ordonnée d'un entier positif n est une manière d'écrire n comme somme d'entiers positifs où l'ordre des termes compte : 1+2 et 2+1 sont deux compositions distinctes de 3, et il en existe toujours exactement 2 à la puissance n moins un au total. Cette capacité prend un unique entier positif n et renvoie chaque composition sous forme de tableau ordonné de parts, ainsi que le décompte total, ce qui vous évite de construire à la main un arbre récursif ou de risquer d'oublier une branche lorsque vous corrigez un devoir, générez des jeux de test ou explorez une combinatoire proche des partitions.

Ce que sont les compositions ordonnées et en quoi elles diffèrent des partitions

En théorie des nombres et en combinatoire, une composition de n est une suite ordonnée d'entiers positifs dont la somme vaut n. Contrairement aux partitions d'entiers, où seul le multiensemble des parts importe et où 1+2 est identifié à 2+1, les compositions traitent chaque ordre comme un objet distinct. Pour tout n supérieur ou égal à un, il existe exactement deux à la puissance n moins un compositions : chaque composition correspond au fait de placer ou d'omettre un séparateur entre deux unités consécutives dans une ligne de n uns.

Les manuels utilisent les compositions lorsque l'ordre encode une séquence, un classement ou une allocation par étapes — par exemple les tailles successives de blocs dans un planning, les longueurs de plages dans une chaîne binaire, ou les tailles de pas le long d'un chemin qui doit couvrir exactement n unités. Les étudiants confondent souvent les deux familles car toutes deux répondent à « comment écrire n comme une somme », mais seules les compositions tiennent compte de l'ordre de gauche à droite.

Renvoyer la liste ordonnée complète rend cette distinction concrète : vous voyez chaque réarrangement, et non un représentant trié canonique, et le champ de décompte doit correspondre à la formule fermée, ce qui vous permet de repérer immédiatement une énumération manuelle incomplète.

Comment la capacité énumère les compositions et quand elle refuse

Le moteur construit chaque composition par expansion récursive de la première part : pour une somme restante r, il essaie chaque taille de part k de un à r, ajoute k au préfixe en cours de construction, et continue jusqu'à ce que le reste soit nul, moment où la suite complétée est enregistrée. Ce parcours produit un ordre stable et déterministe — des requêtes identiques produisent toujours le même tableau de tableaux — sans dépendre d'une horloge, du hasard ou de l'état du réseau.

La réponse indique n lui-même, le tableau des compositions, et un décompte égal à la longueur de ce tableau (qui vaut toujours deux à la puissance n moins un pour un n valide). Un champ n absent, non entier ou mal formé est rejeté de la même façon et n'est jamais facturé.

Où utiliser la liste et ce qu'elle coûte

Les usages typiques incluent la vérification des réponses d'étudiants qui listent les compositions d'un n donné, la génération de cas de test exhaustifs pour des fonctions qui acceptent des suites ordonnées de parts, l'exploration d'identités combinatoires comptant les compositions à tailles de parts restreintes par filtrage a posteriori de la liste complète, et la documentation des options d'échelonnement lorsqu'un budget de n unités peut être découpé en phases ordonnées.

Gardez n dans les bornes documentées pour que la réponse reste maniable ; si vous n'avez besoin que du décompte, vous pouvez toujours utiliser cet outil pour un petit n ou appliquer la formule fermée deux à la puissance n moins un hors de l'outil pour des travaux théoriques plus vastes. Le parcours navigateur s'exécute localement et ne requiert aucun compte. Traitez le décompte renvoyé comme faisant autorité pour les tableaux listés plutôt que de recalculer la longueur dans un code client susceptible de dévier de ce contrat.