Composition d'un nombre entier

mehdi2526

Bonjour à tous, 
J'aimerais savoir s'il existe un algorithme qui donne l'ensemble des compositions d'un nombre entier autre que l'algorithme récursif (qui est de complexité exponentielle). 
Les compositions d'un nombre c'est ses partitions en prenant en compte l'ordre des éléments. Merci d'avance.

LOU16

Bonsoir
Je connais l'ensemble $\mathcal P_n$  des partitions d'un entier $n$. C'est :
$\mathcal P_n= \Big\{(x_1,x_2,\dots x_n)\in \N^n\mid \displaystyle\sum_{k=1}^n kx_k =n\Big\}$

Beaucoup moins  familier m'est celui des "compositions" de $n$. Aussi,en ai-j'été réduit à conjecturer qu'il s'agissait  de:

$\mathcal C_n =\displaystyle \Big\{x\in\bigcup_{k=1}^n (\N^*)^k\mid \sum _{i=1}^k x_i=n\Big\}.\quad\text{Card }(\mathcal C_n)=2^{n-1}$

$\mathcal C_5=\Big\{11111\: ; \:1112 ; \:1121\: ;\: 113\:;\:1211\:;\:122\:;\:131\:;\:14\:;\:2111\:;\:212\;;\:221\:;\:23\:;\:311\:;\:32\:;\:41\:;\:5\Big\}$

Si  par hasard, cette spéculation s'avère correcte, alors on peut munir $ \mathcal C_n$ de l'ordre total "lexicographique" suggéré par l'exemple de $\mathcal C_5$ que j'ai donné, qui rend aisée une énumération algorithmique  , comme celle décrite ci-dessous:

 On part de $x=(1,1\dots1)\in(\N^*)^n$ et tant que $x: =(x_1,x_2,\dots x_k)\neq (n),\:\:x\:$ prend la valeur de son "successeur" $y$ défini par :
$$y \in (\N^*)^{k-2+x_k} , \forall i\in[\![1;k-2]\!], y_i=x_i, \:y_{k-1} =1+x_{k-1},\:\forall i\in[\![k;k-2+x_k]\!], \: y_i=1.$$

L'ensemble des valeurs prises par  $x$  est $\mathcal C_n$

La tâche demandée consistant à énumérer  $2^{n-1}$ objets, je ne vois pas trop comment échapper à une "complexité exponentielle."

mehdi2526

Bonsoir, 
C'est bien la définition des compositions d'un nombre. Je ne l'ai pas encore vérifié, mais j'ai l'impression que ton algorithme est déjà plus efficace que l'algorithme récursif qui consiste à rajouter le nombre "i" au début de toutes les listes déjà construites pour "n-i". Je vais tester cela. Merci pour ta réponse.