Discussion :

[mail.spam]

Bonjour,
je cherche l'algorithme qui donne le nombre de combinaison possible.
Je m'explique j'ai un nombre x d'élément et je cherche à connaitre toutes les combinaison possible.

Exemple j'ai 1 2 3
et je veux énumérer la liste suivante
1
1 2
1 3
1 2 3
2
2 3
3

Connaissez vous l'algorithme
Merci pour votre aide

[SpiceGuid]

Pour le dénombrement :
http://fr.wikipedia.org/wiki/Coeffic...et_statistique



(dans cette formule l'ensemble vide k=0 est considéré comme une solution)

Le dénombrement est constructif, il te donne un algorithme.
Ici il suffira d'énumérer toutes les combinaisons pour k=1 jusqu'à k=n.

[mail.spam]

Merci.
J'ai besoin maintenant d'énumérer cette liste
mais je ne vois pas trop comment faire

[millie]

C'est en fait assez simple.

Si t'as un ensemble S qui contient un élément a et un sous ensemble S' = S-{a}.

L'ensemble des combinaisons de S est l'ensemble des combinaisons de S' + l'ensemble des combinaisons de S' concaténé avec a.

Et si S est l'ensemble vide, il n'y a pas de combinaisons possibles.

C'est donc une propriété récursive qui permet d'écrire ceci

[mail.spam]

MOUAIS..
J'ai pas tout compris.
Si on pouvais m'expliquer ça autrement ça serai gentil.

[millie]

Si on prend l'ensemble : [1,2,3]

Si je note comb(S) la fonction qui donne l'ensemble des combinaisons d'un ensemble
Je note concat(n, C) la concaténation de n à à l'ensemble de combinaisons C
Par exemple :
concat(n, [[1,2,3], [1,2]) = [ [1,2,3,n], [1,2,n] ]

J'ai dit que :
comb([1,2,3]) = concat(1, comb([2,3])) UNION comb([2,3])

Faut calculer comb([2,3]) =
concat(2, comb([3]) UNION comb([3])

Puis comb([3]) = concat(3, comb([])) UNION comb([])) = [[3], []]
(car comb([]) = [[]])

Donc comb([2,3]) = concat(2, [[3],[]]) UNON [[3],[]] = [[2,3], [2], [3], []]
Donc comb([1,2,3]) = concat(1, [[2,3], [2], [3], []) UNION [[2,3], [2], [3], []) = [[1,2,3], [2,1], [3,1], [1], [2,3], [2], [3], []]