Discussion :

[millie]

Bonjour,

Pour ce premier défi, l'équipe de developpez.com vous propose un challenge assez simple pour débuter.

Le problème étant le suivant :

Challenge :
Soit un entier n en entrée,
Déterminer tous les ensembles de nombre entier positif dont la somme vaut n.

Par exemple pour 5, tous les ensembles de nombre dont la somme vaut 5 sont :

• 5
• 4 1
• 3 2
• 3 1 1
• 2 2 1
• 2 1 1 1
• 1 1 1 1 1

A noter que l'on souhaite des ensembles, il n'y a donc pas de doublon (on a une seule fois (3,2), et pas : (3,2) et (2,3) par exemple).

Il n'y a pas de règle sur le format de sortie. Le format standard pour les langages fonctionnels pourra par exemple être une liste de liste :
[[5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1]]

Pour un langage impératif, la sortie pourra simplement être écrite sur la sortie standard.


Les règles

Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :

• la maintenabilité
• la simplicité
• le fait qu'il soit optimisé

Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

Pour répondre, il vous suffit de poster à la suite.

A vos claviers
de votre participation.

__________________________
Sujet proposé par Jedaï

[LLB]

Solution en F# :

Code F# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let sums n =
  let rec sumrec = function
   | 0, _ -> [[]]
   | n, m -> [for i in 1 .. min n m ->> [for j in sumrec((n - i), i) -> i :: j]]
  sumrec(n, n)

Exemple d'appel :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
> sums 5;;
val it : int list list
= [[1; 1; 1; 1; 1]; [2; 1; 1; 1]; [2; 2; 1]; [3; 1; 1]; [3; 2]; [4; 1]; [5]]

[Jedai]

Effectivement, c'est l'algorithme le plus naturel à mon avis, et les "list comprehension" permettent de l'exprimer de façon compacte :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
sums n = csums n n
    where
      csums 0 _ = [[]]
      csums n m = [x:xs | x <- [1..min n m], xs <- csums (n-x) x ]

J'explique la solution :
On utilise une fonction auxiliaire csums() qui prend deux paramètres n et m et renvoie la liste des ensembles de nombres inférieurs à m dont la somme est n.
Cette fonction marche de la façon suivante :
Si n = 0, on considère que l'ensemble vide est la seule solution (dans ce problème on n'utilise pas le 0 dans les solutions, sinon il y en aurait une infinité), d'où le :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

csums 0 _ = [[]]

(le _ peut reconnaître n'importe quoi, on ne se soucie pas de la valeur de m dans ce cas)
Sinon si n > 0 (on ne vérifie pas ici à vrai dire, mais la structure de la fonction fait que si n < 0, elle renverra [], la liste vide, ce qui est correct), alors on utilise un générateur de liste par compréhension, qui ressemble beaucoup à une définition d'ensemble en mathématiques.
En gros la définition mathématiques correspondante serait :
ensemble des "x suivi de xs" tels que x appartient à l'ensemble des entiers de 1 au minimum de n et m et xs appartient à l'ensemble des ensembles de nombres inférieurs à x dont la somme est (n - x).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

csums n m = [x:xs | x <- [1..min n m], xs <- csums (n-x) x ]

le (:) rajoute x au début de la liste xs, vous pouvez voir <- comme "appartient à", et [a..b] signifie "l'ensemble des entiers de a à b" (ça marche aussi avec les autres types énumérables).
En notation mathématique :


Cette algorithme s'appuie donc sur une récursion dont le cas de base est n = 0, ce qui est correct puisqu'à chaque appel récursif le n est diminué mais reste supérieur ou égal à 0. De plus il génère des listes triées dans l'ordre décroissant, ce qui évite les doublons.

--
Jedaï

[Trap D]

Une solution Prolog, simple mais pas optimisée puisqu'elle balaie toutes les solutions, le nettoyage se faisant par un tri puis une élimination des doublons avec le setof.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
% le Predicat d'appel
% N : le nombre a decomposer
% L : la liste des décompositions possibles
decomposition(N, L) :-
	% le setof permet la collecte de tous les resultats
        % et le nettoyage des doublons
	setof(L1, une_decomposition(N,L1), L).

% Le predicat qui fournit une decomposition en somme 
% N : le nombre a decomposer,
% L : la liste resultat triee dans l'ordre naturel croissant
une_decomposition(N, L) :-
	% Le predicat central qui cree la decomposition en somme
	% N  : le nombre à decomposer
	% LN : la liste resultat
	somme(N, LN), 
	% tri de la liste obtenue
	msort(LN, L).

% La condition d'arret du prédicat recursif somme
% Le nombre 0 possède une decomposition vide.
somme(0, []) :- !.


somme(N, [N1 | LN]) :-
	% on prend un nombre quelconque entre 1 et N
	% premier élément de la liste résultat
	between(1, N, N1),
	N2 is N - N1,
	% on complete la liste résultat avec la décomposition
	% du complément à N du premier nombre
	somme(N2, LN).

[Jedai]

Les plus exigeants d'entre vous auront peut-être remarqué que pour l'instant aussi bien ma solution que celle de LLB répètent inutilement certains appels à la fonction auxiliaire (csums dans mon cas, sumrec dans le cas de LLB) durant la récursion... Ces appels pourraient être éliminés en mémorisant les résultats intermédiaires.

Voici une solution utilisant cette optimisation en Haskell :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
sums n = a ! (n,n)
    where
      a = array ( (0,0), (n, n) ) 
          $ ( (0,0), [[]] ) : populateList
      populateList = [( (k,l), [x:xs | x<-[1..l], xs<-a!(k-x, min (k-x) x)] )
                          | k<-[1..n], l<-[1..k]]

a est un tableau (array), ou plutôt une matrice, dont les indices vont de (0,0) à (n,n) (le premier argument de la fonction array donne les bornes de ses indices), et dont les valeurs sont données par la liste associative en second argument.
Une liste associative est une liste de paire (a,b) où a est la clé et b la valeur associée à la clé. Si (a,b) se trouve dans la liste associative, le tableau produit par array() aura la valeur b à l'indice a.
Ici tout le travail est effectué dans cette liste associative : à l'indice (k,l) (pour k variant de 1 à n et l variant de 1 à k), elle associe le résultat de csums k l, sauf qu'au lieu d'appeler récursivement une fonction, elle récupère directement les résultats intermédiaires dont elle a besoin dans le tableau a...

Nous voyons ici l'une des force d'Haskell puisque la définition du tableau a utilise le tableau a. Ceci n'est possible que grâce à la paresse d'Haskell, qui ne calcule une valeur que s'il en a besoin. En conséquence de quoi, les éléments de ce tableau a ne sont calculés qu'à partir du moment où on les utilises, ce qui est le cas lorsqu'on demande "a ! (n,n)" (l'équivalent de a[n][n] ou a[n,n] dans d'autres langages). L'ordre des éléments dans la liste associative n'a aucune importance (bien qu'ici ils soient "dans le bon ordre" par pure coïncidence, cela n'a aucune influence sur l'ordre d'exécution).

Cette version bien que légèrement plus compliquée (mais néanmoins tout à fait abordable puisque j'ai écris cette fonction en moins d'une minute), a des performances très nettement supérieur à la précédente.

Je précise que cette fonction reste complètement dans le paradigme fonctionnel, d'ailleurs le tableau a est fonctionnel puisque immuable.

--
Jedaï

PS : Certains d'entre vous auront peut-être remarqué que la moitié du tableau reste inoccupée et inutile. Il est facile de remédier à cela en définissant un nouveau type Pair x y où x >= y et en en faisant une instance de la type class Ix (Index), mais il s'agit là de sujets avancés d'Haskell, qui ne relèvent pas vraiment du sujet.

[gorgonite]

Une implémentation "triviale" en OCaml... histoire de donner un exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
let rec build_list n m = if n>m then [] else n::(build_list (n+1) m);;

let rec sumrec n =
	match n with
		0 -> [[]]
		|1 -> [[1]]
		|n -> 
			let intervalle = build_list 1 (n-1) in
			List.concat 
				(List.map 
					(fun i -> List.map 
							(fun l -> (n-i)::l) 
							(sumrec (n-i))) 
					intervalle)
;;

let rec print_list l =
	match l with
		[] -> ()
		|a::q -> Printf.printf "%d " a ; print_list q
;;

let rec print lst = 
	match lst with
		[] -> ()
		|a::q -> Printf.printf "[ " ; print_list a ; Printf.printf "] \n" ; print q
;;

let main () =
	print (sumrec (int_of_string Sys.argv.(1)))
;;

main ();;

nb: seule la fonction en gras est nécessaire... mais le reste vous permettra de le compiler, de l'exécuter et de visualiser le résultat tel quel



la complexité temporelle est exponentielle en le premier argument, et l'occupation mémoire l'est aussi (mais c'est le problème qui le veut ) => j'arrive à calculer jusqu'à 17 puis stack overflow

si j'ajoutais la mémorisation des résultats précedemment calculer (on se sert en effet de toutes les valeurs de sumrec i pour 0<i<n pour calculer sumrec n), le temps de calcul serait linéaire, mais la mémoire exploserait plus tot

[LLB]

Les plus exigeants d'entre vous auront peut-être remarqué que pour l'instant aussi bien ma solution que celle de LLB répètent inutilement certains appels à la fonction auxiliaire (csums dans mon cas, sumrec dans le cas de LLB) durant la récursion... Ces appels pourraient être éliminés en mémorisant les résultats intermédiaires.

Tout à fait.

Et juste pour exemple, j'ai traduit le code de Jedai en F# : (fichier complet et exécutable)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
#light
let sums n =
  let rec a = Array2.init (n+1) (n+1) populate
  and populate k l =
    lazy if k = 0 then [[]]
         else [for x in 1 .. min k l ->> [for xs in a.[k-x, x].Force() -> x :: xs]]
  a.[n,n].Force()

Sys.argv.(1) |> int_of_string |> sums |> print_any

Populate est le nom de la fonction d'initialisation du tableau. L'opérateur |> correspond en gros au pipe du Shell (donc, le $ de Haskell à l'envers ). Et comme on fait de la paresse alors que le langage est strict par défaut, il faut appeler la méthode Force (et le mot-clé "lazy").

Utiliser l'évaluation paresseuse n'est pas dans mes habitudes, et je n'y aurais probablement pas pensé sans Jedai, mais je suis plutôt satisfait du résultat. Le code n'est finalement pas trop compliqué.

(Évidemment, les solutions données pour OCaml fonctionnent aussi bien sous F#)