Composition d'un nombre entier

mehdi2526 · February 2023

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 · February 2023

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 · February 2023

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.

Composition d'un nombre entier

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 42