Discussion :

[zhao]

Bonjour a tous .

Voila un probleme que je n'arrive pas a resoudre ( je suis un neophyte ) et pardon pour mon francais je suis etranger .

probleme du loto ( non je ne joue pas car cela n'existe pas dans mon pays ) probleme qui devient une obscetion et faut que j'arrete :-)

j'ai un premier programme qui genere toutes les combinaisons C(x,y) par exemple pour 10 je vais en genrer 210 jusqu'a la c'est facile ensuite j'ai un deuxieme programme qui en fonction des combinaisons que je joue me dit combien j'ai de gagnant a 3 ,4 , 5 , 6 numeros .

Le but c'est d'avoir le minimum de combinaisons a jouer pour etre sur d'avoir 5 bon numeros dans au moins une de mes combinaisons si les 6 numeros gagnant sont parmi ma liste par exemple je veux jouer 10 numeros supposons que les 6 numeros gagnants sont parmi mes 10 et bien j'ai trouvé comme mini ( mais on peut descendre plus bas d'ou mon probleme) 18 combinaisons les voici :

1 2 3 4 5 6
1 2 3 4 7 8
1 2 3 4 9 10
1 2 3 5 7 9
1 2 3 5 8 10
1 2 3 6 7 10
1 2 3 6 8 9
1 2 4 5 7 10
1 2 4 5 8 9
1 2 4 6 7 9
1 2 4 6 8 10
1 2 5 6 7 8
1 2 5 6 9 10
1 2 7 8 9 10
3 4 5 6 7 8
3 4 5 6 9 10
3 4 7 8 9 10
5 6 7 8 9 10

vous pouvez verifier que quelque soit la combinaison que vous prenez parmi les 10 j'aurais au moins une de mes 18 combinaisons qui en auras 5 .

ce resultat je l'ai fait a la main avec mon programme verif_combi voila comment je procede je prends d'office la premiere combi soit 1 2 3 4 5 6 que je met dans un fichier ensuite je rajoute la deuxieme et je test dans verif_combi ce que cela donne ( il faut essayer ce programme pour comprendre ) et je continue en essayant toutes les posisibilitées possible le but c'est trouver le minimum de combinaisons qui me donneras comme rsultat combi a 4=0 combi a 3=0 etc... pour que je n'ai que des combi a 5 et a 6 .
mais a la main c'est tres tres long enfin vous imaginez :-)
donc comment faire pour programmer ce genre de chose y a t'il une ame charitable qui pourrais me le faire peut etre avec un algo de type dichtra ( j'ai lu ca quelque part ) car les chemin possible sont enorme .
merci beaucoup de votre aide.
cordialement

PROGRAMME GENERATEUR DE COMBINAISONS:

Code C :

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
34
35
36
37
 
    #include <stdio.h>
	//  #define nb_boules 8  /* indiquer ici le nombre de numero de votre Loto */
	/*
	 Generer toutes les combinaisons du Loto (Francais, donc avec 49 numeros)
	 Le programme va generer un fichier texte contenant 13983816 combinaisons.
	Compilation :
	gcc -o Loto49 Loto49.c
	*/
 
    	int main(void) {
		 int i,j,k,m,n,p,nb_boules,nb_combi=0,pause;
		 printf("NOMBRE DE BOULES --> ");
		 scanf("%d",&nb_boules);
		 FILE * fichier; /* pointeur sur le fichier de sauvegarde des resultats */
 
		fichier=fopen("combinaisons_brut.txt","w"); /* resultats.txt est le nom du fichier */
 
		 printf("Debut du programme\nPatientez...\n\n");
 
		 for(i=1;i<=nb_boules-5;i++)
		  for(j=i+1;j<=nb_boules-4;j++)
		  for(k=j+1;k<=nb_boules-3;k++)
		  for(m=k+1;m<=nb_boules-2;m++)
		  for(n=m+1;n<=nb_boules-1;n++)
		  for(p=n+1;p<=nb_boules;p++)
		  {
		  nb_combi++;
		  fprintf(fichier,"%d %d %d %d %d %d\n",i,j,k,m,n,p); /* on ecrit les combinaisons dans le fichier */
          }
           fprintf(fichier,"nombre de combinaisons  %d ", nb_combi);
		 fclose(fichier);
		 printf("Le programme a termine. Fin;)\n\n");
		 printf("nombre de combinaisons  %d ", nb_combi);
		 scanf("%d",&pause);;
		 return 0;
	}

*******************************************************************************************

PROGRAMME VERIFICATION DES COMBINAISONS :

Code C :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#include<fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>
#include <time.h>
 
 
main()
{
FILE *fichier ;
int w=0,z=0,f=0,y=0,u=0,max=0,v=0,numscommuns,cptc=0;
float cpt0=0,cpt1=0,cpt2=0,cpt3=0,cpt4=0,cpt5=0,cpt6=0;
int i=0,j=0,k=0,l=0,m=0,n=0,zz=0,a=0,nt=0,xx=0,c=0;
int x[250][6];
int tab[6];
int tc[6];
int line;
float temp_reel=0,temp_ecoule=0;
time_t deb_total,fin_total,deb_reel,fin_reel;
bool stop;
 
//PARCOUR FICHIER ET CHARGEMENT TABLEAU ***************************************
if (fichier =fopen ("Combinaisons.txt", "r")) { //Si ouverture réussie : note le if  pour fopen (alors true soit false)
  while (!feof(fichier)) {
    for (u=0 ; u<6 ; u++) {
      if (fscanf (fichier, "%d", &y)==1)  { x[w][u] = y; }
      }//End for u...
      w++;//Compteur de combinaisons contenues dans le fichier
  }//End while...
 fclose (fichier); //  fermeture du fichier
 if (w>0) { printf("Le fichier contient %d ligne(s)\n", w); }//Vérif lignes lues
}//End if...
else { //Si échec d'ouverture : if fopen retourne false et alors on arrive ici
 printf("Echec a l'ouverture du fichier.\n");
 printf("Appuyez sur n'importe quelle touche pour quitter.");
 getchar();
 exit(0); }
// FIN PARCOUR FICHIER ET CHARGEMENT TABLEAU **********************************
 
 printf("Entrez votre nombre de numeros : ");
scanf("%d",&nt);
//nt=10;
 printf("\n");
 deb_reel=time(NULL);
 a=nt-5;
 
 for(i=1;i<=a;i++)
  for(j=i+1;j<=a+1;j++)
   for(k=j+1;k<=a+2;k++)
    for(l=k+1;l<=a+3;l++)
     for(m=l+1;m<=a+4;m++)
      for(n=m+1;n<=a+5;n++)
{
       tc[0]=i;tc[1]=j;tc[2]=k;tc[3]=l;tc[4]=m;tc[5]=n;
       cptc++;
 
     for (z=0, max=0; z<w ;z++) {        
 
       for (u=0, numscommuns=0; u<6 ; u++) //Comparaison
         for(xx=0; xx<6; xx++) 
           if(x[z][u]==tc[xx]) { numscommuns++; }
 
       if (numscommuns > max) { max = numscommuns; } //Stocker le max trouvé
      }//End z...
 
         if(max==6) { cpt6++; }
         if(max==5) { cpt5++; }
         if(max==4) { cpt4++; }
         if(max==3) { cpt3++; }                        
         if(max==2) { cpt2++; }
         if(max==1) { cpt1++; }
         if(max==0) { cpt0++; }
        // printf("progression : %d\r",cptc);//Vérifie la progression en test 
        // getchar();                       
}//End boucle imbriquée i..n
 
fin_reel=time(NULL);
temp_reel=difftime(fin_reel,deb_reel);
printf("\r");//Effacer la ligne "progression"
printf(" 6 numeros  = %g  fois\n",cpt6);
printf(" 5 numeros  = %g  fois\n",cpt5);
printf(" 4 numeros  = %g  fois\n",cpt4);
printf(" 3 numeros  = %g  fois\n",cpt3);
printf(" 2 numeros  = %g  fois\n",cpt2);
printf(" 1 numeros  = %g  fois\n",cpt1);
printf(" 0 numeros  = %g  fois\n",cpt0);
printf("   TOTAL    = %g\n",cpt6+cpt5+cpt4+cpt3+cpt2+cpt1+cpt0);
printf("\n");
printf("duree reelle de calcul :  %g seconde(s)\n",temp_reel);
scanf(" %d ",nt);
getchar();
}

***************************************************************************************

[KindPlayer]

je suis pas sur de bien comprendre ce que tu veux faire. Compter le nombre de combinaisons parmis toutes celles possibles contenant au moins 5 (ou 6) numéros gagnant? C'est ça? Heu sinon pour calculer les combinaisons c'est pas plus simple de le faire par récurrence?

[zhao]

non je crois pas , si tu suis mon exemple je joue 10 numeros supposons que le tirage du loto les chiffres suivant sortent :
1 4 5 8 9 10 maintenant tu prends mes 18 combinaisons et tu est sur et certain de trouver AU MOINS une combinaisons ayant 5 numeros gagnant , mais on peut reduire encore ce chiffre de 18 a 15 par exemple mais il faut pour cela faire enormement de tests en verifiant avec mon prog verif combi et je le fais a la main donc comment faire voila je pense que c'est plus clair .
en definitive le probleme est COMMENT trouver le minimum de combinaisons a jouer pour etre sur d'avoir au moins 5 bons numeros gagnants si les 6 du tirage sont parmi ma liste de 10 ?

:-)

je suis pas sur de bien comprendre ce que tu veux faire. Compter le nombre de combinaisons parmis toutes celles possibles contenant au moins 5 (ou 6) numéros gagnant? C'est ça? Heu sinon pour calculer les combinaisons c'est pas plus simple de le faire par récurrence?

[pseudocode]

(Réouverture de la discussion)

Suite à la demande du PO, voici une implémentation Java d'un système réducteur. J'ai essayé de commenter au maximum le programme mais n'hésitez par à poster si ce n'est pas clair.

Une classe qui retourne la liste des tirages possibles (combinaisons C(n,p))

Code java :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
/**
 * Enumération des Cnp (stockage sous forme binaire dans un "int") 
 * par exemple
 * 
 * (int)75 = (binaire) 01001011 = (tirage) 1,2,4,7  
 * 
 * @author Xavier Philippeau
 *
 */
public class Cnp {
	private int n,p;
 
	// liste des solutions  
	public int[] results;
 
	// pointeur sur l'element courant de la liste
	private int ptr=0;
 
	public Cnp(int n,int p) {
		this.n=n;
		this.p=p;
 
		// calcul de la taille de la liste des solutions
		// = nombre de combinaisons (n,p) = A(n,p)/!p
		int arrangement = 1, factorielle=1;
		for(int i=0;i<p;i++) {arrangement*=(n-i);factorielle*=(i+1);}
		int combinaison=arrangement/factorielle;
 
		results = new int[combinaison];
 
		build(0,0,0);
	}
 
	// construction recursive des combinaisons possibles
	private void build(int value, int index, int count) {
 
		// impossible de construire une solution
		if ((n-index)<(p-count)) return;
 
		// la combinaison est construite -> ajout a la liste des solutions 
		if (count==p) {
			results[ptr++]=value;
			return;
		}
 
		// explore les 2 chemins possibles pour poursuivre la constuction
 
		// 1. on ne choisit pas l'element numero "index"
		build(value,index+1,count);
 
		// 2. on choisit l'element numero "index"
		build(value+(1<<index),index+1,count+1);
	}
 
	/**
         * Affiche d'une valeur sous forme de chaine texte
         * 
         * @param value valeur sous forme binaire
         * @return la valeur sous forme de chaine texte
         */
	public static String asTicket(int value) {
		StringBuffer sb = new StringBuffer();
		sb.append("[");
		int i=0;
		while(value!=0) {
			i++;
			if ((value & 1)==1) sb.append(i).append(" "); 
			value=value>>1;
		}
		sb.append("]";);
		return sb.toString();
	}
}

La classe du système réducteur avec une heuristique simple, et un methode de monté-carlo pour construire une à une les solutions.

Code java :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import java.util.Arrays;

/**
 * Systeme Reducteur (wheeling system) 
 * 
 * @author Xavier Philippeau
 *
 */
public class SystemeReducteur {

	private final int N,P,K;
	
	/**
	 * @param n,p,k Tirage de P elements parmis N, avec au moins K gagnants
	 */
	public SystemeReducteur(int n, int p, int k) {
		this.N=n;
		this.P=p;
		this.K=k;
	}
	
	/**
	 * Compte le nombre d'elements en commun entre 2 tirages
	 * 
	 * @param value1, value2 2 tirages  
	 * @return le nombre d'elements en commun
	 */
	private int match(int value1,int value2) {
		int and = value1 & value2;
		int bitcount = Integer.bitCount(and);
		return bitcount;
	}
	
	/**
	 * Heuristique pour la recherche des candidats
	 * 
	 * @param value un tirage
	 * @param liste la liste des tirages possibles restants
	 * @return le nombre de fois que ce tirage est gagnant
	 */
	private int score(int value,int[] liste) {
		int score = 0;
		for(int item:liste) {
			if (item==0) continue; // a été supprimé
			int d=match(value,item);
			if (d>=K) score++;
		}
		return score;
	}
	
	/**
	 * retourne la liste des meilleurs tirages
	 * au sens de l'heuristique "score()"
	 * 
	 * @param list la liste des tirages possibles restants 
	 * @return la liste des meilleurs tirages
	 */
	public int[] findCandidats(int[] list) {
		int[] candidats = new int[list.length];
		int count=0;
		
		// recherche exhaustive des meilleures tirages 
		int maxscore=-1;
		for(int item:list) {
			if (item==0) continue; // a été supprimé
			int score = score(item,list);
			if (score>maxscore) {count=0; maxscore=score;}
			if (score==maxscore) candidats[count++]=item;
		}
		return Arrays.copyOf(candidats,count);
	}
	
	/**
	 * Supprime (=mise à zéro) tous les tirages gagnants 
	 * de la liste des tirages possibles
	 * 
	 * @param tirage le tirage de reference
	 * @param list la liste des tirages possibles restants
	 * @return le nombre de tirages possibles restants après suppression
	 */
	public int removeMatching(int tirage, int[] list) {
		int count=0;
		for(int i=0;i<list.length;i++) {
			if (list[i]==0) continue; // a déjà été supprimé
			int match = match(tirage,list[i]);
			if (match>=K) list[i]=0; else count++;
		}
		return count;
	}
	
	/**
	 * retourne une liste des solutions du système de réduction
	 * 
	 * @return la liste des tirages après réduction
	 */
	public int[] computeSolutions() {
		// calcul de la liste de tous les tirages possibles
		int[] tirages = new Cnp(N,P).results;
		int tiragescount=tirages.length;
		
		// allocation de la liste des solutions
		int[] solutions = new int[tirages.length];
		int solutionscount=0;

		// tant qu'il reste des tirages possibles
		while(tiragescount>0) {
			
			// recherche des meilleurs candidats
			int[] candidats = findCandidats(tirages);
			
			// on prend un des candidats, au hasard
			int random = (int)(Math.random()*candidats.length);
			int grille = candidats[random];

			// on ajoute le candidat a la liste des solutions
			solutions[solutionscount++]=grille;

			// on supprime les tirages gagnants de la liste des tirages possibles
			tiragescount=removeMatching(grille, tirages);
		}
		
		// on retourne la liste des solutions 
		return Arrays.copyOf(solutions, solutionscount);
	}
	
	// ------------------------------------------------------------------------
	
	/**
	 * Main: Test du systeme reducteur  
	 */
	public static void main(String[] args) {
		// creation du Systeme Reducteur 10/6/5
		SystemeReducteur tf = new SystemeReducteur(10,6,5);
		
		// calcul des solutions et conserve la meilleure
		int[] bestsolution = null;
		for(int loop=0;loop<100;loop++) {
			int[] solutions = tf.computeSolutions();
			if (bestsolution==null || solutions.length<bestsolution.length) { 
				System.out.println("found a solution of size:"+solutions.length);
				bestsolution=solutions;
			}
		}

		// affiche la meilleure solution
		for(int solution:bestsolution)
			System.out.println(Cnp.asTicket(solution));
	}
}

Résultat pour un systeme 10/6/5

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
 
found a solution of size:16
found a solution of size:15
found a solution of size:14
[2 3 4 7 9 10 ]
[1 2 5 6 7 10 ]
[1 4 6 8 9 10 ]
[3 4 5 6 7 8 ]
[1 2 3 5 8 9 ]
[1 4 5 7 8 9 ]
[3 4 5 6 9 10 ]
[1 2 3 4 6 7 ]
[2 6 7 8 9 10 ]
[1 2 4 5 8 10 ]
[1 3 5 7 8 10 ]
[1 3 6 7 9 10 ]
[2 3 4 6 8 10 ]
[2 4 5 6 7 9 ]

[zhao]

Bonjour
Pseudocode un seul mot MILLES MERCIS :-)

bon maintenant la question bete ( avant de m'attaquer a ton source:-) ) je voudrais savoir quel sont les etapes a faire pour executer ce programme car je ne connais que le C

autre question je trouve que ton programme est court si je compare avec du C est ce normal ou as tu optimiser ton programme ?

cordialement

je crois comprendre "en gros" ton algo c'est tres beau :-) petites questions :
pourrais tu m'expliquer cette ligne :

* (int)75 = (binaire) 01001011 = (tirage) 1,2,4,7


et celle ci :

@param value valeur sous forme binaire
@return la valeur sous forme de chaine texte

cordialement

[pseudocode]

@param et @return sont dans une zone de commentaire /*...*/ donc ils ne servent a rien d'utile pour le programme.

* (int)75 = (binaire) 01001011 = (tirage) 1,2,4,7

C'est une atuce pour le stockage. Par exemple, pour le tirage 1,2,4,7 on pourrait utiliser un talbeau de 4 int:

int tirage[4];
tirage[0]=1; tirage[1]=2; tirage[2]=4; tirage[3]=7;

Mais ca prend beacoup de place et ce n'est pas facile a manipuler (copier, comparer, ...). La technique que j'utilise permet de représenter un tirage sur un seul "int".

J'utilise le fait qu'un entier a une représentation en binaire en mémoire:
(int)0 = (binaire) 00000000
(int)1 = (binaire) 00000001
(int)2 = (binaire) 00000010
(int)3 = (binaire) 00000011
etc.

Je fais chaque correspondre chaque bit avec un numero de boule. Si le bit=1, alors la boule fait partie du tirage, sinon elle n'en fait pas partie:

(binaire) 00000001 = boule #1 sélectionnée
(binaire) 00000010 = boule #2 sélectionnée
(binaire) 00000100 = boule #3 sélectionnée
(binaire) 00001000 = boule #4 sélectionnée
etc...

donc la combinaison:
(binaire) 01001011 = boules #1 + #2 + #4 + #7 sélectionnées

et ce nombre (binaire) 01001011 est equivalent a l'entier (int)75.