cs_ghada
Messages postés2Date d'inscriptionsamedi 28 août 2004StatutMembreDernière intervention30 août 2004
-
30 août 2004 à 11:14
adrientaieb -
11 févr. 2005 à 13:51
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
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006 30 août 2004 à 11:45
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
cs_JCDjcd
Messages postés1138Date d'inscriptionmardi 10 juin 2003StatutMembreDernière intervention25 janvier 20094 30 août 2004 à 13:59
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)
Rusalie
Messages postés21Date d'inscriptiondimanche 18 juillet 2004StatutMembreDernière intervention24 août 2004 30 août 2004 à 21:40
(jcdjcd) Je me permets un commentaire: Sans intention péjorative; C’est un code en écriture Arabe de droite à gauche, la « dague » que l’on affûte pour trouver les combinaisons, on recolle un bout sur la liste, les fausses complications, c’est presque lubrique, mesquin.
« Salamalèc et Malécoum salam » (désolé pour la syntaxe).