Probleme – Compter au lieu d'optimiser : combinaisons ou compositions ?

1. Les deux programmes ne diffèrent que par l'ordre des boucles :

/* (A) pieces a l'exterieur */
int a[S + 1]; a[0] = 1; for (int s = 1; s <= S; s++) { a[s] = 0; }
for (int i = 0; i < k; i = i + 1) {
    for (int s = p[i]; s <= S; s = s + 1) { a[s] = a[s] + a[s - p[i]]; }
}

/* (B) sommes a l'exterieur */
int b[S + 1]; b[0] = 1; for (int s = 1; s <= S; s++) { b[s] = 0; }
for (int s = 1; s <= S; s = s + 1) {
    for (int i = 0; i < k; i = i + 1) {
        if (p[i] <= s) { b[s] = b[s] + b[s - p[i]]; }
    }
}

2. Ce que chacun compte.

• (A) compte les combinaisons : les multi-ensembles de pièces, sans tenir compte de l'ordre. La boucle extérieure sur les pièces impose un ordre de considération : quand on traite la pièce $p_i$, toutes les façons déjà comptées n'utilisent que $p_0,\dots ,p_{i-1}$. On ne peut donc jamais compter deux fois le même multi-ensemble dans deux ordres différents.
• (B) compte les compositions : les suites de pièces, l'ordre comptant. La boucle extérieure sur $s$ laisse toutes les pièces disponibles à chaque étape, et $1+2$ est compté séparément de $2+1$.

Vérification à la main, $S=5$ et $P=\{1,2\}$.

Combinaisons : $1+1+1+1+1$, $1+1+1+2$, $1+2+2$ — trois.

Compositions, énumérées par le programme :

(1,1,1,1,1) (1,1,1,2) (1,1,2,1) (1,2,1,1) (1,2,2) (2,1,1,1) (2,1,2) (2,2,1)

huit.

3. Les deux suites, pour $S=0$ à $8$ et $P=\{1,2\}$ :

S              0  1  2  3  4  5  6  7  8
(A) combinaisons  1  1  2  2  3  3  4  4  5
(B) compositions  1  1  2  3  5  8 13 21 34

La seconde ligne est la suite de Fibonacci, et ce n'est pas un accident : une composition de $s$ avec des $1$ et des $2$ commence par un $1$ (il reste $s-1$) ou par un $2$ (il reste $s-2$), donc $C(s)=C(s-1)+C(s-2)$. La première ligne vaut $\lfloor s/2\rfloor +1$ : le nombre de $2$ détermine la combinaison.

Avec $P=\{1,2,5\}$ et $S=10$, la mesure donne $10$ combinaisons contre $128$ compositions.

La morale, et elle vaut pour tout le chapitre. On a écrit deux algorithmes en croyant en écrire un. Ni l'un ni l'autre n'est faux : ils répondent à deux questions différentes, et le code ne dit pas laquelle. L'ordre des boucles est une partie de la spécification — au même titre que le sens de parcours de l'exercice sur le sac à dos en une ligne, et pour la même raison profonde : il décide de ce qui est déjà écrit dans la table quand on la lit.