Combinaison des entiers

J'aime bien avoir un algorithme qui permet de générer toutes les combinaisons d'une liste d'entiers c'est à dire 2^n avec n le nombre d'entiers de la liste. par exemple pour 1,2,3 je génére 1,2,3,12,13,23

Je connais un algorithme qui fait ca, mais il est recursif et de complexite exponentielle (ce qui est inevitable puisqu il y a 2^n listes possibles).
Il se base sur le fait que si tu prend un nombre de la liste de base (1,2,3,...n), toutes les combinaisons sont celles sans ce nombre + les memes mais avec ce nombre.
A partir de la l implementation vient facilement, tout du moins en Caml (j ai fait cet algo cet annee en cours).

Si je me souviens bien en caml ca donne :

let rec ajout a l = a::l;;

let rec combin l=
match l with
|[]->[]
|a::reste->let l2=combin reste in (map (ajout a) l2)@l2;;

Je n en suis plus tres sur mais ca doit etre ca.
Maintenant si tu comprends le Caml ca devrais aller

Oui il est vrai que l'on peut le faire par recursivite, c'est d'ailleurs le meme principe de la formule de Pascal (avec les Cnp).

avec CPlex, ça le fait tt seul


Magic Nono: l'informagicien!

euh... ca fait pas 2^n combinaisons...
-----------------------------------------------
Tout ce qui ne tue pas rend plus fort !

Ben si, le nombre de sous ensemble d'un ensemble a n elements est 2^n, d'ailleurs c'est pourquoi on note les sous parties de N, 2^N (par abus) et de R, 2^R (toujours par abus). (il est vrai que dans l'exemple avec 1,2,3, il manque des combinaisons : {} et {1,2,3}, ensemble vide, ou l'univers)

1 2 3
2 3 1
3 1 2
3 2 1
2 1 3
1 3 2

2^3=8
ici 6 combinaisons !

=2*3? je C plus, j'ai horreur des math

Magic Nono: l'informagicien!

ici il n'y a que qu'un ensemble, puisque l'ordre ne compte pas.
les 8 combinaisons sont :
#1 : {}
#2 : {1}
#3 : {2}
#4 : {3}
#5 : {1,2}
#6 : {1,3}
#7 : {2,3}
#8 : {1,2,3}

de toute maniere il est certain que le nombre de sous ensemble est 2^n ( on ne va pas refaire les mathematique), cela se demontre tres facilement.

>> Magic Nono

ce que tu as fait la, je pense que c'est les permutations et non les combinaisons, auquel cas il y en a effectivement 6.

ui, C bien ce qu'il me semblait....

merci

Magic Nono: l'informagicien!