Composition d'un nombre entier
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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\}$
$$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.$$
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.