Somme d'entiers naturels

L'objectif de cet exercice est de trouver toutes les décompositions d'un entier n en la somme de p entiers naturel de 1 à 9.

Par exemple, l'entier 27 possède 11 décompositions en somme de 5 entiers allant de 1 à 9 :

[[9; 8; 7; 2; 1]; [9; 8; 6; 3; 1]; [9; 8; 5; 4; 1]; [9; 8; 5; 3; 2];
 [9; 7; 6; 4; 1]; [9; 7; 6; 3; 2]; [9; 7; 5; 4; 2]; [9; 6; 5; 4; 3];
 [8; 7; 6; 5; 1]; [8; 7; 6; 4; 2]; [8; 7; 5; 4; 3]]

et 3 avec 4 entiers:

 [[9; 8; 7; 3]; [9; 8; 6; 4]; [9; 7; 6; 5]]

1. 1

   Indice

   Utiliser un filtrage de motif sur la liste pour ajouter systématiquement le nouvel élément en tête de chaque sous-liste rencontrée.
   Écrire une fonction map_prepend : 'a -> 'a list list -> 'a list list qui renvoie la liste de listes obtenue en ajoutant l'élément k en tête de chaque sous-liste de lst. Par exemple map_prepend 0 [[1;2]; [3]] renvoie [[0;1;2]; [0;3]].
2. 2

   Indice

   Définir une fonction interne qui explore toutes les décompositions commençant par k (en commençant par le plus grand) jusqu'à contenir p éléments. Pour les conditions d'arrêt : combien y a-t-il de façons de choisir 0 élément ? Est-il possible de décomposer 0 en r (différent de 0) éléments ?
   Écrire une fonction partition : int -> int list list qui renvoie la liste de toutes les parties de taille p de l'ensemble {1; ...; 9}, chaque partition étant représentée par une liste de listes d'entiers triées en ordre décroissant. Par exemple partition 1 renvoie [[9]; [8]; [7]; [6]; [5]; [4]; [3]; [2]; [1]] et partition 2 renvoie :

     [[9; 8]; [9; 7]; [9; 6]; [9; 5]; [9; 4]; [9; 3]; [9; 2]; [9; 1]; [8; 7];
      [8; 6]; [8; 5]; [8; 4]; [8; 3]; [8; 2]; [8; 1]; [7; 6]; [7; 5]; [7; 4];
      [7; 3]; [7; 2]; [7; 1]; [6; 5]; [6; 4]; [6; 3]; [6; 2]; [6; 1]; [5; 4];
      [5; 3]; [5; 2]; [5; 1]; [4; 3]; [4; 2]; [4; 1]; [3; 2]; [3; 1]; [2; 1]]
    ```

3. 3

   Indice

   Générer toutes les combinaisons possibles puis appliquer un filtre basé sur la somme des éléments pour isoler les résultats valides.
   Écrire une fonction decompositions_force_brute : int -> int -> int list list qui renvoie toutes les décompositions de l'entier n en exactement p entiers distincts de {1; ...; 9} triées en ordre décroissant. Par exemple decompositions_force_brute 6 2 renvoie [ [5;1]; [4;2] ].
4. 4

   Indice

   Parcourir les valeurs possibles du plus grand au plus petit et compléter récursivement le reste de la somme en imposant une contrainte de décroissance.
   Écrire une fonction completions : int -> int -> int -> int list list qui renvoie la liste de toutes les décompositions de n en exactement p entiers compris entre 1 et max_val, chaque décomposition étant triée en ordre décroissant. Cette fonction utilise le backtracking :
   • Condition d'arrêt : si la décomposition trouvée comporte p éléments dont la somme est n, on conserve cette décomposition, sinon ce n'est pas une solution.
   • Coupe franche : si la somme de la décomposition est plus grande que n ou s'il n'y a plus de nombre à additionner (et n non nul), alors ce n'est pas une solution non plus.
   • Appel récursif : les solutions potentielles sont celles qui comportent le nombre courant ou qui ne le comporte pas. Par exemple completions 5 2 4 renvoie [ [4;1]; [3;2] ].
5. 5

   Indice

   Invoquer la fonction de complétion existante en spécifiant explicitement la borne supérieure égale à neuf pour obtenir le résultat final.
   En déduite une fonction decompositions_backtracking : int -> int -> int list list qui renvoie les décompositions de n en exactement p entiers distincts de {1; ...; 9} en appelant directement la fonction précédente avec max_val = 9. Par exemple decompositions_backtracking 6 2 renvoie [ [5;1]; [4;2] ].