[resolu] renvoyer les termes de combinaison des C(n,k)

renvoyer les termes de combinaison des C(n,k) [resolu] - C++ - Programmation

Marsh Posté le 22-07-2002 à 11:34:15    

Salut,je cherche a renvoyer les combinaisons des C(n,k)
exemple je passe n et k en parametre et je veux
 
les n et les k pouvant etre de l ordre de 100 ou 200
 
si n=2 et k=4
1,2 1,3 1,4
2,3 2,4
3,4
 
kelkun aurait une idee de la facon de traiter le probleme
(est-ce que je dois calculer d abord le nombre de termes?)
 
Merci!
 
PS: un code ou un morceau serait le bien venu!
 
bonne journee a tous et a toutes!


Message édité par nicolasm le 23-09-2002 à 15:31:35
Reply

Marsh Posté le 22-07-2002 à 11:34:15   

Reply

Marsh Posté le 22-07-2002 à 13:56:13    

http://forum.hardware.fr/icones/flag1.gif interessé

Reply

Marsh Posté le 22-07-2002 à 14:15:17    

je vois aps trop ce que tu essaye de faire  :??:


---------------
Le Tyran
Reply

Marsh Posté le 22-07-2002 à 14:24:23    

letoII a écrit a écrit :

je vois aps trop ce que tu essaye de faire  :??:  




 
 
je cherche a obtenir tout les couples des combinaisons
nouvel exemple  
j ai n=3 et p=5
je veux toutes les combinaisons de trois elements
soit 1,2,3  
     1,2,4  
     1,2,5
     
     1,3,4
     1,3,5
 
     1,4,5
 
     2,3,4
     2,3,5
 
     2,4,5
 
     3,4,5
 
C plus clair?

Reply

Marsh Posté le 22-07-2002 à 14:29:12    

Ha oui comme ça c plus clair. :D


---------------
Le Tyran
Reply

Marsh Posté le 22-07-2002 à 15:30:34    

JeSuisPasUnNumero a écrit a écrit :

http://forum.hardware.fr/icones/flag1.gif interessé




 
Si tu trouves de ton cote merci de me l envoyer!
niko

Reply

Marsh Posté le 22-07-2002 à 15:39:13    

t'as un gros disque j'espère pour stocker les valeurs car pour n=200 et k=200 tu as 200!/(100!*100!) possibilités.
(200! = factorielle(200) = 200 * 199 *198 * .... * 2 * 1)
 

Reply

Marsh Posté le 22-07-2002 à 15:40:28    

Soit g rien compris, soit tu veux le triangle de pascal :??:


---------------
©2008 Bleuarff Corp.
Reply

Marsh Posté le 22-07-2002 à 15:45:01    

Bleuarff a écrit a écrit :

Soit g rien compris, soit tu veux le triangle de pascal :??:




 
Non,ce que je veux c les combinaisons de N parmi P
mais pas leur valeur ,ce que je veux ce sont tout les tuples
soit l ensemble E ={a,b,c}  C(2,3)={a,b}{a,c}{b,c}
 
et moi ce que je veux c est recuperer {a,b} puis {a,c} puis {b,c}
voila

Reply

Marsh Posté le 22-07-2002 à 15:47:50    

JPA a écrit a écrit :

t'as un gros disque j'espère pour stocker les valeurs car pour n=200 et k=200 tu as 200!/(100!*100!) possibilités.
(200! = factorielle(200) = 200 * 199 *198 * .... * 2 * 1)
 




 
 
en fait on a revu a la baisse, seul les p sont tres gros et les n
ne depassent pas 20 pour le stockage ca sera dans un fichier au pire, si t as une idee hesite pas!
 
niko

Reply

Marsh Posté le 22-07-2002 à 15:47:50   

Reply

Marsh Posté le 22-07-2002 à 15:49:11    

nicolasm a écrit a écrit :

 
 
Non,ce que je veux c les combinaisons de N parmi P
mais pas leur valeur ,ce que je veux ce sont tout les tuples
soit l ensemble E ={a,b,c}  C(2,3)={a,b}{a,c}{b,c}
 
et moi ce que je veux c est recuperer {a,b} puis {a,c} puis {b,c}
voila
 




 
En gros il faut que tu imbriques k boucles parmi les n elements mais en évitant les doublets et en eliminant les permutations. Je pense que la solution se situe dans un algo recursif.

Reply

Marsh Posté le 22-07-2002 à 16:26:22    

M'enfin cptet une conneire, je suis pas certain d'avoir compris ce que yu veux donc voila...
 
soit E l'ensemble

Code :
  1. procedure cnk_ens(n,p:integer);
  2. var i,j:integer;
  3. begin
  4. for i:=0 to high(E) do
  5.  for j:=i+1 to high(E) do
  6.   writeln('{',E[i],',',E[j],'}');
  7. end;


 
fo vraiment qe je m'emmerde a mon stage pour arriver a faire du code pour d'autres...


---------------
©2008 Bleuarff Corp.
Reply

Marsh Posté le 22-07-2002 à 16:50:57    

Bleuarff a écrit a écrit :

M'enfin cptet une conneire, je suis pas certain d'avoir compris ce que yu veux donc voila...
 
soit E l'ensemble

Code :
  1. procedure cnk_ens(n,p:integer);
  2. var i,j:integer;
  3. begin
  4. for i:=0 to high(E) do
  5.  for j:=i+1 to high(E) do
  6.   writeln('{',E[i],',',E[j],'}');
  7. end;


 
fo vraiment qe je m'emmerde a mon stage pour arriver a faire du code pour d'autres...




 
C presque ca mais ca fait que les combinaisons de deux variables moi il me les faut toutes C(3,9) ne marchent pas par ex !
merci qd meme de ton aide et bon stage
 
PS c koi ton langage la c du pseudo code?


Message édité par nicolasm le 22-07-2002 à 16:52:57
Reply

Marsh Posté le 23-07-2002 à 10:46:52    

C du pascal ça, je sais pas faire grand-chose d'autre pour le moment :(
 
Sinon je vois pas pkoi ça te va pas...tu veux ausis touts les combinaisons qui te vont pas ? tu remplaces le

Code :
  1. for j:=i+1 to high(E)...

par

Code :
  1. for j:=1 to high(E)


---------------
©2008 Bleuarff Corp.
Reply

Marsh Posté le 23-07-2002 à 11:10:27    

Bleuarff a écrit a écrit :

C du pascal ça, je sais pas faire grand-chose d'autre pour le moment :(
 
Sinon je vois pas pkoi ça te va pas...tu veux ausis touts les combinaisons qui te vont pas ? tu remplaces le

Code :
  1. for j:=i+1 to high(E)...

par

Code :
  1. for j:=1 to high(E)






 
En fait ce que tu me propose n est valable que pour les
C(2,p) et pas pour les C(n,p) car ton algo n est pas recursif c ca le probleme!mais merci quan meme

Reply

Marsh Posté le 23-07-2002 à 12:09:02    

putain je viens de comprendre le truc... :ouch: en effet me recursif semble obligatoire...g rien a foutre je vais voir ce que je peux faire...


---------------
©2008 Bleuarff Corp.
Reply

Marsh Posté le 23-07-2002 à 13:26:40    

Bon c'est assez facile en fait:
 

let rec combirec k l s = match k with  
  |0 -> print_string (s^"\n" )  
  |_ ->(match l with  
       |[] -> ()
       |a::r -> ( (match s with
         | "" -> combirec (k-1) r (a)  
         | _ -> combirec (k-1) r (s^","^a));
         combirec k r s;
       )
  );;
 
combirec 3 ["1";"2";"3";"4";"5"] "";;


 
bon faudrait essayer de le modifier pour le rendre recursif terminal
 
resultat:  

#1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5
- : unit = ()


 
LeGreg

Reply

Marsh Posté le 23-07-2002 à 13:28:16    

c quoi ça, du C++ ? Je comprends rien...


---------------
©2008 Bleuarff Corp.
Reply

Marsh Posté le 23-07-2002 à 13:29:14    

ca marche aussi pour autre chose que des nombres  
 

combirec 3 ["rouge";"jaune";"vert";"bleu";"indigo";"violet"] "";;


 
resultat:

#rouge,jaune,vert
rouge,jaune,bleu
rouge,jaune,indigo
rouge,jaune,violet
rouge,vert,bleu
rouge,vert,indigo
rouge,vert,violet
rouge,bleu,indigo
rouge,bleu,violet
rouge,indigo,violet
jaune,vert,bleu
jaune,vert,indigo
jaune,vert,violet
jaune,bleu,indigo
jaune,bleu,violet
jaune,indigo,violet
vert,bleu,indigo
vert,bleu,violet
vert,indigo,violet
bleu,indigo,violet
- : unit = ()


 
A+
LeGreg

Reply

Marsh Posté le 23-07-2002 à 13:30:17    

oops on est dans le forum "C, c++"..
desole j'avais pas vu
enfin c'est adaptable en C++ mais c'est moins compact..
 
LeGreg

Reply

Marsh Posté le 23-07-2002 à 13:54:58    

Voila une traduction a peu pres litterale du code caml
donc c'est peut-etre moins performant:
 

Code :
  1. #include <string>
  2. #include <iostream>
  3. using namespace std;
  5. typedef char* lpstrz ;
  7. void combirec(int k, lpstrz l[], const string &s) {
  8.   if (k==0) {
  9.     cout << s << endl;
  10.     return;
  11.   }
  12.   if (*l==0) return;
  13.   if (s.empty())
  14.   {
  15.     combirec(k-1, l+1, *l);
  16.   }
  17.   else
  18.   {
  19.     combirec(k-1, l+1, s+","+*l);
  20.   }
  21.   combirec(k, l+1, s);
  22. }
  24. int main() {
  25.   lpstrz tableau[] = {"1", "2", "3", "4", "5", 0};
  26.   combirec(3, tableau, "" );
  27.   return 0;
  28. }


 
et la sortie:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5


 
LeGreg


Message édité par LeGreg le 23-07-2002 à 14:02:42
Reply

Marsh Posté le 23-07-2002 à 18:26:40    

legreg a écrit a écrit :

Voila une traduction a peu pres litterale du code caml
donc c'est peut-etre moins performant:
 

Code :
  1. #include <string>
  2. #include <iostream>
  3. using namespace std;
  5. typedef char* lpstrz ;
  7. void combirec(int k, lpstrz l[], const string &s) {
  8.   if (k==0) {
  9.     cout << s << endl;
  10.     return;
  11.   }
  12.   if (*l==0) return;
  13.   if (s.empty())
  14.   {
  15.     combirec(k-1, l+1, *l);
  16.   }
  17.   else
  18.   {
  19.     combirec(k-1, l+1, s+","+*l);
  20.   }
  21.   combirec(k, l+1, s);
  22. }
  24. int main() {
  25.   lpstrz tableau[] = {"1", "2", "3", "4", "5", 0};
  26.   combirec(3, tableau, "" );
  27.   return 0;
  28. }


 
et la sortie:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5


 
LeGreg




 
MERCI BCP y a un peu de C++ MAIS JE L ADAPTERAI EN C ET PUIS C SYMPA DE TA PART
PS:C KOI LE LANGAGE ZARBI AVANT?
 

Reply

Marsh Posté le 23-07-2002 à 19:06:05    

euh le langage precedent c'est du Caml
c'est un des langages de choix des algorithmiciens
a cause de sa simplicité et de son efficacité.
C'est un langage moitié fonctionnel/moitié impératif.
 
C++ essaie de copier certaines features des langages
fonctionnels (par les templates, pointeurs de fonctions, recursivité) mais n'y arrive pas aussi bien.
 
Caml n'est plus maintenu sauf dans la version qui est utilisée
par l'éducation nationale, il y a une version orientée objet qui est mise a jour ( http://www.ocaml.org/ ).
 
Par exemple, il m'a fallu reflechir un moment avant
de sortir la bonne version en C++ du programme, alors que c'est assez naturel en CAML (une fois qu'on connait la syntaxe).
 
A+
LeGReg

Reply

Marsh Posté le 25-07-2002 à 02:31:40    

Le problème étant horrible...
...ma solution est horrible ! (mais elle marche)
Exemple pour un ensemble de caractères:

Code :
  1. //////////////
  2. //Combiner.h//
  3. //////////////
  4. #include <malloc.h>
  6. #define dimof(a) ( sizeof(a)/sizeof(a[0]) )
  7. #define CombinerM(n,ae) Combiner(n, alloca(n*sizeof(int)), dimof(ae), ae##Callback )
  9. typedef void (*pvf)() ; //pvf: pointeur de fonction sans arguments ne retournant rien
  10. void Combiner(int numCases, int* tabCases, int numElm, pvf callback) ;
  12. //////////////
  13. //Combiner.c//
  14. //////////////
  15. #include "Combiner.h"
  17. //éléments privés
  18. static int  ni ; //nombre d'indices
  19. static int* ai ; //tableau d'indices de combinaisons
  20. static int  ne ; //nombre d'éléments
  21. static pvf  fn ; //pointeur sur la fonction de rappel
  23. //partie récursive (à usage interne)
  24. static void CombinerRec(int ii, int vali){
  25. if(ii==ni) //profondeur de récursion maximum
  26.  fn(); //appel pour combinaison prête
  27. else
  28.  for( ai[ii]=vali ; ai[ii]<ne ; ++ai[ii] ){ //compter avec cet indice
  29.   CombinerRec(ii+1, ai[ii]+1) ; //récursion avec l'indice suivant commençant à 1 de plus
  30.  }
  31. }
  33. //élément public
  34. void Combiner(int numCases, int* tabCases, int numElm, pvf callback){
  35. if(numElm<numCases || numCases<1) //si pas assez d'éléments ou pas de cases...
  36.  return ; //...erreur, ne rien faire
  37. ni=numCases ;
  38. ai=(int*)alloca(ni*sizeof(int)) ;
  39. ne=numElm ;
  40. fn=callback ;
  41. CombinerRec(0,0) ;
  42. }
  44. /////////////////
  45. //utilisateur.c//
  46. /////////////////
  47. #include <stdio.h>
  48. #include "Combiner.h"
  50. //exemple de tableau d'éléments
  51. char tabElems[] = {'a','b','c','d','e'} ;
  53. //exemple de fonction de rappel correspondante
  54. void tabElemsCallback(){ //à chaque passage ici, une nouvelle combinaison valide est dans ai[]...
  55. int i;
  56. for(i=0 ; i<ni ; ++i)
  57.  printf( "%c,",tabElems[ ai[i] ] ) ;//affiche l'élément n° i
  58. printf("\b.\n" ) ; //effacer la dernière virgule, nouvelle ligne
  59. }
  61. //exemple de test
  62. int main() {
  63. //appel normal
  64. int tabIndices[3] ; //recevra les combinaisons
  65. Combiner(dimof(tabIndices), tabIndices, dimof(tabElems), tabElemsCallback) ;
  66. printf("\n" ) ;
  68. //appel simplifié via une macro
  69. CombinerM(3,tabElems) ;
  71. return 0;
  72. }

Cela dit, ce serait beucoup plus propre avec les classes et patrons du C++.


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 25-07-2002 à 11:51:18    

Citation :

Le problème étant horrible...
...ma solution est horrible ! (mais elle marche)


 
Elle te plaisait pas ma solution?
 
LeGreg

Reply

Marsh Posté le 26-07-2002 à 00:53:01    

legreg a écrit a écrit :

Elle te plaisait pas ma solution?


Le string n'existant pas en C, fallait bien y remédier... et c'est pas simple !
J'ai également aménagé la possibilité de combiner n'importe quoi, et de faire autre chose que afficher.
 
A noter que je me suis concentré sur les performances, d'où une certaine "obfuscation".


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 26-07-2002 à 04:10:32    

legreg a écrit a écrit :

Bon c'est assez facile en fait:
 

let rec combirec k l s = match k with  
  |0 -> print_string (s^"\n" )  
  |_ ->(match l with  
       |[] -> ()
       |a::r -> ( (match s with
         | "" -> combirec (k-1) r (a)  
         | _ -> combirec (k-1) r (s^","^a));
         combirec k r s;
       )
  );;
 
combirec 3 ["1";"2";"3";"4";"5"] "";;


 
bon faudrait essayer de le modifier pour le rendre recursif terminal
 
resultat:  

#1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5
- : unit = ()


 
LeGreg




 
waou....
 
ça c'est du language limpide  [:sisicaivrai]

Reply

Marsh Posté le 26-07-2002 à 10:50:06    

bjone a écrit a écrit :

 
waou....
ça c'est du language limpide  [:sisicaivrai]  




 
Ah la version en C est tout de suite plus claire :D.
 
LeGreg

Reply

Marsh Posté le 26-07-2002 à 16:49:16    

petit test:
pour calculer les 13983816 combinaisons du loto:
391 millisecondes
(la recursivité n'est pas un probleme)
 
par contre pour les afficher: 1heure..
(il faudrait presque les afficher sous Dos,
la console windows est vraiment trop lente)
 
LeGreg

Reply

Marsh Posté le 26-07-2002 à 18:54:25    

c plus simple de les foutre dans un fichier et attrapper notepad :D

Reply

Marsh Posté le 27-07-2002 à 00:55:37    

J'ai déjà eu le problème.
Je voulais chronométrer le calcul de nombres premiers, je me retrouvais à mesurer la vitesse d'affichage :pt1cable: .
 
Il est loin le premier test en Basic interprété sur un Apple II qui prenait 1 mn pour atteindre 1000...


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 27-07-2002 à 12:06:06    

legreg a écrit a écrit :

 
 
Ah la version en C est tout de suite plus claire :D.
 
LeGreg



:non: pas si on a déja fait du caml :sol:  
 
En prolog ça doit être plus clair pour les non initié


---------------
A suivre
Reply

Marsh Posté le 28-07-2002 à 04:17:58    

Même quand on a l'algorithme correctement décrit, il reste encore à faire des choix d'implémentation.
La solution dépend des points fort et faibles du langage choisi...
 
Je rêves parfois d'un langage de description d'algorithmes capable de générer le code correspondant dans des langages différents, en choisissant au mieux entre récusion/boucles pointeurs/indices pré-allocation/dynamisme tests avant/après ect...
 
Je dis que le problème des combinaisons est horrible parce que:

  • Le nombre de "cases" n'est pas connu à la compilation: récursion obligée.
  • La dernière récursion doît connaître l'état des précédentes: mémorisation indispensable (dynamique puisque nombre pas connu à la compilation)
  • La mémorisation exige une initialisation à la première récursion: récursion contrariée.


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 29-07-2002 à 00:43:50    

Citation :

Je dis que le problème des combinaisons est horrible parce que:

  • Le nombre de "cases" n'est pas connu à la compilation: récursion obligée.
  • La dernière récursion doît connaître l'état des précédentes: mémorisation indispensable (dynamique puisque nombre pas connu à la compilation)
  • La mémorisation exige une initialisation à la première récursion: récursion contrariée.


tu n'exageres pas un peu ?
 
LeGreg

Reply

Marsh Posté le 29-07-2002 à 02:05:25    

Je trouves pas.
Ça fait partie de ces problèmes très simples à énoncer mais compliqués à résoudre (la solution dépend beaucoup du langage).
 
J'oubliais:

  • Renvoi à l'appelant d'un grand nombre de valeurs.


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 29-07-2002 à 07:45:22    

ca m'a l'air tout de meme assez fortement lineaire  
=> l'enoncé déboule directement sur la solution optimale.
 
Je pensais a un probleme dérivé:
trouver l'ensemble E minimal de combinaisons a 6 chiffres parmi 49 telles que l'on ait au moins une combinaison gagnante a 5 chiffres. (pour toute combinaison c de C(5,49), il existe une combinaison c' de E telle que c est inclue dans c';).
Quelqu'un a une idée un peu fine?
 
LeGreg

Reply

Marsh Posté le 01-08-2002 à 13:16:17    

legreg a écrit a écrit :

ca m'a l'air tout de meme assez fortement lineaire  
=> l'enoncé déboule directement sur la solution optimale.
 
Je pensais a un probleme dérivé:
trouver l'ensemble E minimal de combinaisons a 6 chiffres parmi 49 telles que l'on ait au moins une combinaison gagnante a 5 chiffres. (pour toute combinaison c de C(5,49), il existe une combinaison c' de E telle que c est inclue dans c';).
Quelqu'un a une idée un peu fine?
 
LeGreg




 
Y en a qu on deja essaye de calculer des probas en integrant les 5000 dernieres sorties du loto mais ca marche pas au mieux tu gagnes 20f pour 18 depenser et pour un travail de ouf!!!
 
En tout cas je vois que mon probleme vous a bien fait reflechir

Reply

Marsh Posté le 02-08-2002 à 01:11:12    

Euh...
 
Les probabilités n'aident en rien pour un jeu de hasard pur comme le Loto.
Les statistiques sur les nombres joués peuvent servir.
 
Ce sujet a déjà été beaucoup débattu...


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 02-08-2002 à 23:47:36    

il ne s'agit pas de proba pour gagner au loto
il s'agit d'un bete probleme d'algo :)
 
LeGreg

Reply

Marsh Posté le 03-08-2002 à 00:34:11    

nicolasm a écrit a écrit :

Y en a qu on deja essaye de calculer des probas en integrant les 5000 dernieres sorties du loto mais ca marche pas au mieux tu gagnes 20f pour 18 depenser et pour un travail de ouf!!!


Il parle bien de probabilités pour gagner au Loto, non ?
 
Sinon je vais chercher pour le problème des ensembles gagnants.


Message édité par Musaran le 03-08-2002 à 00:35:20

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed