Discussion :

[zhao]

Bonjour pseudocode et tout le monde :-)
Bon me revoilà ( oui je sais je suis tenace ;-) ) j'ai trouvé une nouvelle façon de réduire les combinaisons si une personne sympathique pouvait me le traduire en C et en JAVA cela serais très très sympathique et ensuite ensemble du moins les personnes intéressé on pourrais l'optimiser pour essayer de trouver le MINI a chaque fois car avec cet algo pour 10 6 5 je trouve 15 alors que le mini est de 14 mais je pense que les passionnées comme moi de ce genre de problèmes ensemble on résoudra ce problème l'avantage de cet algo c'est qu'il marche quelque soit le numéros et me semble assez rapide donc merci de votre aide pour le porg enC et en JAVA .
voici l'algo ( heu je suis nulle en algo donc pardon pour les puristes ;-) )

cordialement

Pour une garantie N-X/Y
-Calcul de toutes les grilles de 6 numéros pour N numéros. Par exemple si N=10, les grilles sont 1,2,3,4,5,6 - 1,2,3,4,5,7 - 1,2,3,4,5,8... jusqu'à 5,6,7,8,9,10
Calcul de toute les grille de Y numeros pour N numeros selon le même principe. par exemple si N=10 et Y=4, les grilles sont 1,2,3,4 - 1,2,3,5 - 1,2,3,6... jusqu'à 7,8,9,10
On prends la 1ère grille à 6 numéros ; donc 1,2,3,4,5,6 et on effectue un groupement des grilles à Y numéros. Le groupement consiste à supprimer de la liste des grilles à Y numéros toutes les grilles répondant aux critères X/Y. Voyons par l'exemple :
- Imaginons une garantie N-3/4
- On prend donc la grille à 6 num. 1,2,3,4,5,6
- On prend chaque grille à Y num, en commençant par la première qui est donc 1,2,3,4
- On teste : est ce que parmi les numéros de la grille à 6 num (1,2,3,4,5,6) il y a X numéros similaires (donc 3 dans l'exemple : N-3/4) dans la grille à Y num ? Si non, on garde la grille à Y num et on continue les tests avec la grille à Y num suivante. Si oui on supprime la grille à Y num de la liste des grilles à Y num.
- Une fois toutes les grilles à Y num testées, on note le nombre de grilles supprimées (notons S par exemple).
- On supprime la grille à 6 num de la liste des grilles à 6 num et on rajoute cette même grille à la liste des grilles définitive de la garantie.
- On effectue les mêmes tests avec toutes les grilles à 6 num mais sans supprimer de grilles à Y num, on note juste quelle est la grille à 6 num qui supprime le plus de grille à Y num. Optimisation : si on trouve une grille à 6 num qui supprime autant de grilles à Y num que S alors on prend cette grille à 6 num sans continuer les tests( mais je pense qu'il y a d'autres optimisations possible )
- On utilise la meilleure grille à 6 num que l'on a trouvé. On supprime donc de nouveau la grille à 6 num de la liste des grilles à 6 num et on rajoute cette même grille à la liste des grilles définitives de la garantie. On effectue également le groupement (suppression comme plus haut des grilles à Y num de la liste des grilles à Y num).
- On continue ainsi les tests jusqu'à ce qu'il ne reste aucune grille à Y num dans la liste des grilles à Y num.


bien entendu le programme devras être fait de façon a ce que nous puissions choisir N , X et Y .
merci de votre aide .

Je m'adresse au specialiste de la combinatoire ou de l'algo je sais pas tres bien .

objectif toujours lié au loto :
quel est le minimum de grille a jouer pour être sur d'avoir au moins 5 bons numéros si les 6 chiffre gagnants sont parmi ma selection :

supposons que je veux jouer les 8 chiffres suivant :
1 2 3 4 5 6 7 8 et que le jour du tirage les 6 numeros sont parmi ses 8 .

nombre de combinaisons de 6 parmi 8 =28 les voici :

1 2 3 4 5 6 -1 2 3 4 5 7 - 1 2 3 4 5 8 - 1 2 3 4 6 7 - 1 2 3 4 6 8 - 1 2 3 4 7 8
1 2 3 5 6 7 -1 2 3 5 6 8 - 1 2 3 5 7 8 - 1 2 3 6 7 8 - 1 2 4 5 6 7 - 1 2 4 5 6 8
1 2 4 5 7 8 -1 2 4 6 7 8 - 1 2 5 6 7 8 - 1 3 4 5 6 7 - 1 3 4 5 6 8 - 1 3 4 5 7 8
1 3 4 6 7 8 -1 3 5 6 7 8 - 1 4 5 6 7 8 - 2 3 4 5 6 7 -2 3 4 5 6 8 -2 3 4 5 7 8
2 3 4 6 7 8 - 2 3 5 6 7 8 -2 4 5 6 7 8 - 3 4 5 6 7 8

bon j'espere ne pas en avoir oublier .

maintenant on va creer des paires comme ceci .
chaque combinaisons est compose de 6 chiffres
1 2 3 4 5 6 on prends les paires :

A=1-2 B=3-4 c=5-6 d=7-8

et on va faire tous les arrangements ( je sais pas si cela s'appelle des arrangement donc...) des groupes de 3 paires donc .

ABC
ABD
ACD
BCD

maintenant on va mettre les chiffres corrspondant a ses paires.
ABC=1 2 3 4 5 6
ABD=1 2 3 4 7 8
ACD=1 2 5 6 7 8
BCD=3 4 5 6 7 8

et bien vous pouvez prendre n'importe laquelle des combinaisons parmi les 28 possible je suis sur a 100% qu'au moins une de mes 4 combinaisons auras au moins 5 bon numeros .

question pourquoi cela ne marche pas avec 10 11 12 25 30 ...etc...
peut etre qu'il y a un truc a changer pour les autres numeros qui a trait a la combinatoire ? ou y a t'il un probleme logique etc???
bref je ne comprends pas :-)
cordialement

[Zavonen]

Bonjour Zhao,
Ta persévérance et ta détermination sont émouvantes.
Il ne faut pas en perdre le sommeil.
Je n'ai pas tout compris dans ta méthode. Pas pour un problème de langue, tu es parfaitement compréhensible, mais c'est la description de l'algo que j'ai du mal à saisir.
A priori tout me semble faisable, mais je n'ai pas une vue d'ensemble du procédé. Ce qui ne veut pas dire que cela puisse marcher 'grandeur nature'.
J'hésite bien franchement à passer derrière Pseudocode qui propose presque toujours le meilleur du meilleur.
En tout cas, à tout hasard, j'ai écrit 3 fonctions de base.
C'est en python un langage interprété de très haut niveau qui n'est pas particulièrement performant, mais qui est parfait pour faire des essais, quand le truc fonctionne on peut le reprogrammer en C.
Python est libre de droit tu peux télécharger le package gratuitement et il vient avec un EDI appelé IDLE qui te permet de tester des programmes de les modifier etc...
Je peux éventuellement continuer si tu me dis pas à pas ce que tu veux faire.

Code python :

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
# -*- coding: cp1252 -*-
 
#générer les combinaisons de p éléments de E
def Combinaisons(E,p):
    n=len(E)
    G=[[0],[1]]
    for i in range (0,n-1):
        G= [y+[x] for y in G for x in [0,1]]
    H=[X for X in G if reduce(lambda x,y:x+y,X)==p]
    return [[E[i] for i in range(0,n) if X[i]==1 ] for X in H]
 
#calcule le nombre d'éléments communs aux listes X,Y
def communs(X,Y):
    n=0;
    for x in X:
        if x in Y:
            n+=1
    return n
 
 
def main():
    N=range(1,11)# les nombres de 1 à 10
    A=Combinaisons(N,6)
    B=Combinaisons(N,4)
 
if __name__ == '__main__':
    main()

[zhao]

Bonjour Zavonen :-)

Le but je pense que tu le connais ,trouver un algo qui me permette de jouer ( je precise qd meme que je ne joue pas c'est vraiment pour comprendre enfin bref pour etre moins idiot :-) ) le minimum de grille qui me permette d'avoir au minimum une grille a 5 numeros si les 6 numeros sorti sont parmi ma liste .
maintenant l'algo pas de probleme il fonctionne meme bien je l'ai tester a la main hummm vraiment penible .

supposons que je veux jouer 8 numeros 1 2 3 4 5 6 7 8 et que les numeros sorti sont par exemple 1 4 5 6 7 8 ( ou n'importe laquelle des 28 possibles) je vais essayer de trouver un algo me permettant de jouer un minimum de grilles avec une certitude d'avoir au moins 5 bon numeros .

ALGO EXEMPLE .

dans un premier le temps je prends toutes les combinaisons de 6 parmi 8 donc 28 les voici que je vais appeller tab1
ensuite je vais crer dans notre exemple ( mais cela peut etre autre chose suivent la garantie voulue)
la liste des combinaisons en garantie 5/6 pour 8 donc la c'est la meme chose je vais les mettre dans tab2
d'office je prends la premiere ligne de tab1 et je compare cette combinaison avec toute les combinaisons de tab2 si j'ai au moins 5 bons numeros en commun je supprime cette combinaison .
une fois ce premier test terminé j'ai supprimé exactement 13 combinaisons et il me reste 15 combinaisons que je met dans reste
maintenant la demarche change :
la premiere combinaison qui m'as servi CAD 1 2 3 4 5 6 je la met dans mon tiroire VALID
je prends ensuite la 2ieme combinaison CAD 1 2 3 4 5 7 et je compare avec toute les combinaisons de RESTE ( car n'oublier pas que mon tab2 a ete reduit) et je fais la meme chose mais la differance c'est que je ne supprime pas "ENCORE" les combinaisons je NOTE simplement combien elle peut en supprimer je passe a la troisieme de tab1 CAD 1 2 34 5 8 et je fais la meme operation quand toute les combi de tab1 aurons tester les combi de RESTE ( la il y a pas mal d'optimisation a faire et j'ai quelque idée ;-) ) je prends la combinaisons de tab1 qui auras le nombre de suppression potentiel le plus grand et je supprime ses combinaisons de RESTE et je met la combinaison qui eu le plus grand potentiel dans VALID et je continue jusqu'as ce que RESTE =0 et ça marche aucun probleme la dessus -)

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
19
20
21
22
23
24
25
26
27
28
29
30
 
tab1                 tab2                          reste
 1 2 3 4 5 6        1 2 3 4 5 6                 1 2 3 4 7 8
 1 2 3 4 5 7        1 2 3 4 5 7                 1 2 3 5 7 8
 1 2 3 4 5 8        1 2 3 4 5 8                 1 2 3 6 7 8
 1 2 3 4 6 7        1 2 3 4 6 7                 1 2 4 5 7 8
 1 2 3 4 6 8        1 2 3 4 6 8                 1 2 4 6 7 8
 1 2 3 4 7 8        1 2 3 4 7 8                 1 2 5 6 7 8
 1 2 3 5 6 7        1 2 3 5 6 7                 1 3 4 5 7 8
 1 2 3 5 6 8        1 2 3 5 6 8                 1 3 4 6 7 8
 1 2 3 5 7 8        1 2 3 5 7 8                 1 3 5 6 7 8
 1 2 3 6 7 8        1 2 3 6 7 8                 1 4 5 6 7 8
 1 2 4 5 6 7        1 2 4 5 6 7                 2 3 4 5 7 8
 1 2 4 5 6 8        1 2 4 5 6 8                 2 3 4 6 7 8
 1 2 4 5 7 8        1 2 4 5 7 8                 2 3 5 6 7 8
 1 2 4 6 7 8        1 2 4 6 7 8                 2 4 5 6 7 8
 1 2 5 6 7 8        1 2 5 6 7 8                 3 4 5 6 7 8
 1 3 4 5 6 7        1 3 4 5 6 7
 1 3 4 5 6 8        1 3 4 5 6 8
 1 3 4 5 7 8        1 3 4 5 7 8
 1 3 4 6 7 8        1 3 4 6 7 8
 1 3 5 6 7 8        1 3 5 6 7 8
 1 4 5 6 7 8        1 4 5 6 7 8
 2 3 4 5 6 7        2 3 4 5 6 7
 2 3 4 5 6 8        2 3 4 5 6 8
 2 3 4 5 7 8        2 3 4 5 7 8
 2 3 4 6 7 8        2 3 4 6 7 8
 2 3 5 6 7 8        2 3 5 6 7 8
 2 4 5 6 7 8        2 4 5 6 7 8
 3 4 5 6 7 8        3 4 5 6 7 8

desolé mais les espaces entre tab1 tab2 et reste ne sont pas apparue je ne sais pas pourquoi .

je voulais preciser que quand "RESTE" seras vide les combinaisons que j'aurais mis dans VALID repondrons a mes exigences sur a 100% :-)

ah au fait Zavonen rassure toi je dort tres bien :-)
non certaines personnes on pour dada les voitures ,la tele,lecinema etc... moi c'est ce genre choses et oui je suis perseverant malheureusement je n'ai pas les connaissances theorique( math,algo etc.. ) mais bon je les apprends ici :-)

[Zavonen]

Voici un programme qui fait exactement ce que tu veux:

Code python :

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
# -*- coding: cp1252 -*-
 
#générer les combinaisons de p éléments de E
def Combinaisons(E,p):
    n=len(E)
    G=[[0],[1]]
    for i in range (0,n-1):
        G= [y+[x] for y in G for x in [0,1]]
    H=[X for X in G if reduce(lambda x,y:x+y,X)==p]
    return [[E[i] for i in range(0,n) if X[i]==1 ] for X in H]
 
#calcule le nombre d'éléments communs aux listes X,Y
def communs(X,Y):
    n=0;
    for x in X:
        if x in Y:
            n+=1
    return n
 
# liste des éléments à conserver dans T2 selon le critère nombre d'éléments avec L <p
def Conserver(T2,L,q):
    return [X for X in T2 if communs(X,L)<q]
 
#Calcule combien de combinaisons X peut supprimer dans R sur la base de p éléments communs au moins
def PeutSupprimer(X,p):
    global Reste
    H=[L for L in Reste if communs(X,L)>=p]
    return len(H)
 
# détermine la combinaison qui supprime le plus de combinaisons dans T1
def TrouveSuivant(p):
    global Tab1
    s=PeutSupprimer(Tab1[0],p)
    S=Tab1[0]
    for X in Tab1:
        t= PeutSupprimer(X,p)
        if t >s:
            s=t
            S=X
    return S
 
# enleve l'élement X de la liste L
def Enleve(X,L):
    return [Y for Y in L if Y !=X]
 
# effectue le traitement indiqué
def Traite(p):
    global Reste, Valid,Tab1,Tab2
    while Reste !=[]:
        X=TrouveSuivant(p)
        Reste=Conserver(Reste,X,p)
        Valid.append(X)
        Tab1=Enleve(X,Tab1)
 
#variables globales
Valid=[]
Tab1=[]
Tab2=[]
Reste=[]
 
def main():
    global Reste,Tab1,Tab2,Valid
    N=range(1,9)# les nombres de 1 à 8
    Tab1=Combinaisons(N,6)
    Tab2=Combinaisons(N,6)
    Reste=Conserver(Tab2,Tab1[0],5)
    Valid.append(Tab1[0])
    Tab1=Tab1[1:] # on enlève la première
    Traite(5)
    print Valid
 
if __name__ == '__main__':
    main()

[zhao]

pour info pour 8 il me garde 4 combinaisons pour 10 il m'en garde 15 sniff pas encore 14 qui est le minimum :-)

aussi vite que ça ? vous me donnez des complexes toi et pseudocode :-)

tu me disais plus haut qu'une fois un programme python fait on peut le reprogrammer en C comment ? sait tu le faire car le C au moins je connais un peu et la ça serais genial -)

[Zavonen]

Je n'en trouve que 4 dans Valid:
Attention je ne commence pas avec 1,2,3,4,5,6

[[3, 4, 5, 6, 7, 8], [1, 2, 5, 6, 7, 8], [1, 2, 3, 4, 7, 8], [2, 3, 4, 5, 6, 8]]

[zhao]

oui c'est normal car tu l'as lancé pour 8 et tes 4 combinaisons sont bonne mais faut le lancer pour 10 et la tu doit trouver 15 si tu trouve 15 c'est gagné :-)
ensuite si cela t'amuse on pourras penser a l'optimisation .

par exemple au debut on traite la premiere combinaisonde tab1 ( ou une autre cela n'as pas d'importance car la premiere quel que soit sa place supprimeras toujours autant de combi que les autre et ce quelque soit la combi prise je l'ai verifié ) mais par souci de simplicité prenon la premiere elle va donc supprimer de tab2 beaucoup de combi commencant par 1 ensuite quand on prends la deuxieme vu que deja beaucoup de combi commencant par 1 sont suuprimer il serais plus judicieux de prendre la derniere de tab1 ensuite la deuxieme ensuite l'avant derniere ce qui devrais permettre de ganer quesque test , enfin je sais pas si je m'exprime bien :-)
enfin je pense qu'il y a pas mal de trucs a faire dans le domaine de l'optimisation et en dernier essayer de comprendre pourquoi avec cette methode je n'arrive pas au minimum je doit faire une erreur de logique quelque part mais ou ?? :-)

Je n'en trouve que 4 dans Valid:
Attention je ne commence pas avec 1,2,3,4,5,6

[Zavonen]

Moi je trouve 17:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
def main():
    global Reste,Tab1,Tab2,Valid
    N=range(1,11)# les nombres de 1 à 10
    Tab1=Combinaisons(N,6)
    Tab2=Combinaisons(N,6)
    Reste=Conserver(Tab2,Tab1[0],5)
    Valid.append(Tab1[0])
    Tab1=Tab1[1:] # on enlève la première
    Traite(5)
    print Valid
    print len(Valid)

>>>
[[5, 6, 7, 8, 9, 10], [2, 3, 4, 8, 9, 10], [2, 3, 4, 5, 6, 7], [1, 4, 6, 7, 9, 10], [1, 3, 5, 7, 8, 10], [1, 2, 5, 6, 8, 9], [1, 3, 4, 7, 8, 9], [1, 3, 4, 5, 6, 10], [1, 2, 6, 7, 8, 10], [2, 4, 5, 7, 9, 10], [1, 2, 3, 6, 9, 10], [1, 2, 4, 5, 6, 8], [3, 5, 6, 7, 8, 9], [1, 2, 3, 4, 7, 9], [4, 6, 7, 8, 9, 10], [4, 5, 7, 8, 9, 10], [3, 5, 6, 8, 9, 10]]
17

[Zavonen]

Après la première étape il y a 185 éléments dans Reste
Voici le processus de réduction (à chaque fois on diminue).

25
25
21
21
21
13
13
11
10
8
6
4
3
2
1
1

[zhao]

bon il y a probablement une erreur quelque part car il y en a 15 sur et certain .
premiere etape ok il en reste 185 .
ensuite tu prends bien 1 2 3 4 5 7 et tu compare avec les 185 combinaison tu note combien 1 2 3 4 5 6 7 supprime de combinaisons et tu passe a 1 2 3 4 5 8 que tu compare avec les 185 tu note combien 1 2 3 4 5 8 supprime de combinaisons et tu passe a .........5 6 7 8 9 10 que tu compare avec toutes les 185 tu note combien supprime de combinaisons maintenant tu prends la combinaisons compris entre 1 2 3 4 5 7 et 5 6 7 8 9 10 qui supprime le plus de combinaison et tu la met dans VALID et tu ote les combinaisons dans reste CORRESPONDANT a la combinaisons que tu as mis dans VALID je crois que l'erreur vient de la ou un probleme de tableau .

erreur dans cette ligne escuse

"ensuite tu prends bien 1 2 3 4 5 7 et tu compare avec les 185 combinaison tu note combien 1 2 3 4 5 6 7 " ce n'est pas 1 2 3 4 5 6 7 MAIS BIEN SUR 1 2 3 4 5 7 :-)

autre erreur possible prenons par exemple les 2 premieres combinaisons que tu met dans VALID soit [5, 6, 7, 8, 9, 10], [2, 3, 4, 8, 9, 10]
ses 2 combinaisons bien sur ne sont plus dans TAB1 vu que tu les met dans VALID on est bien ok ? ensuite quand tu attaque la troisieme recherche tu recommence bien au debut de TAB1 ?

[Zavonen]

As-tu installé l'interprète python pour exécuter mon code ?

[Zavonen]

Je crois qu'il n'y a pas d'erreur. J'ai modifié le programme ainsi.
Supprimé Tab[2] (ne sert à rien).
Fait tous les traitements (y compris le premier) dans la fonction traite.
Ecris et appelé une fonction de trace Voir, qui montre à chaque fois.
La longueur de Tab1, la longueur de Reste, le dernier élément entré dans Valid.
Je trouve bien 17, et tu peux voir la progression:

Code python :

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
# -*- coding: cp1252 -*-
 
#générer les combinaisons de p éléments de E
def Combinaisons(E,p):
    n=len(E)
    G=[[0],[1]]
    for i in range (0,n-1):
        G= [y+[x] for y in G for x in [0,1]]
    H=[X for X in G if reduce(lambda x,y:x+y,X)==p]
    return [[E[i] for i in range(0,n) if X[i]==1 ] for X in H]
 
#calcule le nombre d'éléments communs aux listes X,Y
def communs(X,Y):
    n=0;
    for x in X:
        if x in Y:
            n+=1
    return n
 
# liste des éléments à conserver dans T2 selon le critère nombre d'éléments avec L <p
def Conserver(T2,L,q):
    return [X for X in T2 if communs(X,L)<q]
 
#Calcule combien de combinaisons X peut supprimer dans R sur la base de p éléments communs au moins
def PeutSupprimer(X,p):
    global Reste
    H=[L for L in Reste if communs(X,L)>=p]
    return len(H)
 
# détermine la combinaison qui supprime le plus de combinaisons dans T1
def TrouveSuivant(p):
    global Tab1
    s=PeutSupprimer(Tab1[0],p)
    S=Tab1[0]
    for X in Tab1:
        t= PeutSupprimer(X,p)
        if t >s:
            s=t
            S=X
    return S
 
# enleve l'élement X de la liste L
def Enleve(X,L):
    return [Y for Y in L if Y !=X]
 
#trace pour constater l'avancement
def Voir():
    global Reste, Valid,Tab1
    print len(Tab1),len(Reste),Valid[-1]
 
 
# effectue le traitement indiqué
def Traite(p):
    global Reste, Valid,Tab1
    Reste=Conserver(Reste,Tab1[0],5)
    Valid.append(Tab1[0])
    Tab1=Tab1[1:] # on enlève la première
    Voir()
    while Reste !=[]:
        X=TrouveSuivant(p)
        Reste=Conserver(Reste,X,p)
        Valid.append(X)
        Tab1=Enleve(X,Tab1)
        Voir()
 
#variables globales
Valid=[]
Tab1=[]
Reste=[]
 
def main():
    global Reste,Tab1,Valid
    N=range(1,11)# les nombres de 1 à 10
    Tab1=Combinaisons(N,6)
    Reste=Combinaisons(N,6)
    Traite(5)
 
if __name__ == '__main__':
    main()

>>>
209 185 [5, 6, 7, 8, 9, 10]
208 160 [2, 3, 4, 8, 9, 10]
207 135 [2, 3, 4, 5, 6, 7]
206 114 [1, 4, 6, 7, 9, 10]
205 93 [1, 3, 5, 7, 8, 10]
204 72 [1, 2, 5, 6, 8, 9]
203 59 [1, 3, 4, 7, 8, 9]
202 46 [1, 3, 4, 5, 6, 10]
201 35 [1, 2, 6, 7, 8, 10]
200 25 [2, 4, 5, 7, 9, 10]
199 17 [1, 2, 3, 6, 9, 10]
198 11 [1, 2, 4, 5, 6, 8]
197 7 [3, 5, 6, 7, 8, 9]
196 4 [1, 2, 3, 4, 7, 9]
195 2 [4, 6, 7, 8, 9, 10]
194 1 [4, 5, 7, 8, 9, 10]
193 0 [3, 5, 6, 8, 9, 10]
>>>

[zhao]

Bonjour Zavonen :-)
pourrais tu commencer par la premiere combinaisons CAD 1 2 3 4 5 6 et la garder (VALID) .

[zhao]

comme je l'ai dit dans un autre post au debut la premiere combinaison de TAB1 supprime toutes le meme nombre de combinaisons de TAB2 MAIS ce ne sont pas les memes combinaisons il est bien evident que 1 2 3 4 5 6 et dans ton exemple [5, 6, 7, 8, 9, 10] vont bien supprimer chacune 25 combi de TAB2 mais bien entendu les combi de TAB2 supprimé serons tres differantes ce qui va tout changer pour la suite dans mon ALGO je dit CECI :

Imaginons une garantie N-3/4
- On prend donc la grille à 6 num. 1,2,3,4,5,6
- On prend chaque grille à Y num, en commençant par la première qui est donc 1,2,3,4
- On teste : est ce que parmi les numéros de la grille à 6 num (1,2,3,4,5,6) il y a X numéros similaires (donc 3 dans l'exemple : N-3/4) dans la grille à Y num ? Si non, on garde la grille à Y num et on continue les tests avec la grille à Y num suivante. Si oui on supprime la grille à Y num de la liste des grilles à Y num.
- Une fois toutes les grilles à Y num testées, on note le nombre de grilles supprimées (notons S par exemple).
- On supprime la grille à 6 num de la liste des grilles à 6 num et on rajoute cette même grille à la liste des grilles définitive de la garantie.
- On effectue les mêmes tests avec toutes les grilles à 6 num mais sans supprimer de grilles à Y num, on note juste quelle est la grille à 6 num qui supprime le plus de grille à Y num. Optimisation : si on trouve une grille à 6 num qui supprime autant de grilles à Y num que S alors on prend cette grille à 6 num sans continuer les tests( mais je pense qu'il y a d'autres optimisations possible )
- On utilise la meilleure grille à 6 num que l'on a trouvé. On supprime donc de nouveau la grille à 6 num de la liste des grilles à 6 num et on rajoute cette même grille à la liste des grilles définitives de la garantie. On effectue également le groupement (suppression comme plus haut des grilles à Y num de la liste des grilles à Y num).
- On continue ainsi les tests jusqu'à ce qu'il ne reste aucune grille à Y num dans la liste des grilles à Y num.

[Zavonen]

Zhao,
Inutile de renvoyer à chaque fois l'intégralité de mes messages. Cela surcharge inutilement la base de données des posts.
J'ai fait ce que tu me suggères, commencer par [1,2,3,4,5,6].
Il n'y a rien de changé je trouve toujours 17.
Voici l'exécution:

209 185 [1, 2, 3, 4, 5, 6]
208 160 [2, 3, 4, 8, 9, 10]
207 135 [2, 3, 4, 5, 6, 7]
206 114 [1, 4, 6, 7, 9, 10]
205 93 [1, 3, 5, 7, 8, 10]
204 72 [1, 2, 5, 6, 8, 9]
203 59 [1, 3, 4, 7, 8, 9]
202 46 [1, 3, 4, 5, 6, 10]
201 35 [1, 2, 6, 7, 8, 10]
200 25 [2, 4, 5, 7, 9, 10]
199 17 [1, 2, 3, 6, 9, 10]
198 11 [1, 2, 4, 5, 6, 8]
197 7 [3, 5, 6, 7, 8, 9]
196 4 [1, 2, 3, 4, 7, 9]
195 2 [4, 6, 7, 8, 9, 10]
194 1 [4, 5, 7, 8, 9, 10]
193 0 [3, 5, 6, 8, 9, 10]

Il y a peut-être une explication. J'applique strictement l'algo que tu me donnes. C'est un algo. répondant à la définition d'algorithme 'glouton'. A chaque étape tu cherches la combinaison qui élimine le maximum d'éléments de Reste. Du point de vue de l'optimisation générale ce n'est peut être pas ce qu'il y a de mieux à faire. J'explique: tu constates que la combinaison qui élimine le plus de candidats en élimine 12 puis celle d'après 5, total: 17. Si tu avais examiné les paires tu en aurais peut être trouvé une qui élimine 9 et l'autre 9 aussi à elles deux 18 >17.

[zhao]

HUmm cela a l'air d'etre une tres bonne idée tu peut essayer ? moi de mon coté je vais me taper a la main pour verifier ou je fais une erreur dans l'explicatio de mo ALGO car je trouve bien 15 mais comme j'avais plein de brouillons j'ai tout jeter faut que je recommence mais c'est pas grave :-)
pour l'instant je n'installe pas ton code car je ne connais pas Python une fois que le resultat seras bon la je m'attaquerais a ton programme et a python :-)

[Zavonen]

Je viens d'essayer une méthode purement aléatoire (chaque combinaison est tirée au hasard complètement dans Tab1).
J'ai fait des statistiques sur un grand nombre d'expériences. Il s'avère que la moyenne de la longueur de Valid est de l'ordre de 42 !!!!
Ce qui prouve que si tu es absolument sûr que le minimum absolu est 15, ton algo glouton n'est pas mauvais du tout.

[zhao]

Je crois avoir trouver l'erreur et c'est de ma faute car je suis en train de me taper tout a la main pour 10 t'imagine le boulot :-)

je crois que j'ai oublier de preciser que supposons que la combi XX de TAB1 supprime 10 combi de RESTE et que la combi YY de TAB1 supprime egalement 10 combi de RESTE la bonne combi a garder est XX et non YY meme si il supprime le meme nombre de combi dans RESTE donc la condition est strictement > cela a une grande importance car la aussi les combi supprime ne serons pas les memes peut tu essayer par curiosité car je suis sur du papier et j'ai completement oublier de le dire ( humm pas terrible le zhao il y a encore du boulot ;-) )

voila les 15 combinaisons qui se trouve dans valid :

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

[Zavonen]

J'ai vérifié, ça marche !
L'exécution donne bien 0 et 15.
Il reste que ton ensemble n'a pas été obtenu par l'algorithme glouton que tu décris, et que j'ai utilisé.

Code Python :

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
# effectue le traitement indiqué
def Traite(p):
    global Reste, Valid,Tab1
    Sol=[[1, 2, 3, 4, 5, 6],[1, 2, 3, 7, 8, 9],[1, 4, 5, 7, 8, 10],[2, 4, 6, 7, 9, 10],[3, 5, 6, 8, 9, 10],[1, 2, 3, 4, 8, 10],[1, 2, 5, 6, 7, 8],[1, 3, 4, 5, 7, 9],[2, 3, 5, 6, 7, 10],  [2, 4, 5, 6, 8, 9],[1, 2, 5, 6, 9, 10],[1, 3, 4, 6, 7, 8],[1, 3, 6, 8, 9, 10],[2, 3, 4, 5, 7, 9], [2, 3, 7, 8, 9, 10]]
    for X in Sol:
        Reste=Conserver(Reste,X,p)
        Valid.append(X)
        Tab1=Enleve(X,Tab1)
def main():
    global Reste,Tab1,Valid
    N=range(1,11)# les nombres de 1 à 10
    Valid=[]
    Tab1=Combinaisons(N,6)
    Reste=Combinaisons(N,6)    
    Traite(5)
    print len(Reste)
    print len(Valid)

[Zavonen]

Bon finalement j'ai eu un peu de mal à classer les combinaisons dans l'ordre.
Cela fait j'obtiens exactement le même résultat que toi (exactement les mêmes éléments dans Valid et dans le même ordre).
Voici donc la version définitive:

Code python :

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
# -*- coding: cp1252 -*-
import random
 
#décide si la décomposition de n en binaire comporte exactement p chiffres 1.
def hpcb(n,p):
    s=0
    while n:
        s+=n%2
        n=n/2
    return s==p
# retourne tous les nombres entre 0 et n-1 ayant p fois le chiffre 1 en système binaire
def fcar(p,n):
    return [i for i in range(0,n) if hpcb(i,p)]
 
# associe une partie de L à p élément à un nombre
def assoc(L,h):
    k = len(L)-1
    M=[L[k-i] for i in range(0,k+1)]
    result=[]
    i=0
    while h:
        r=h%2
        if r:
            result.append(M[i])
        h=h/2
        i+=1
    result.reverse()
    return result
 
# retourne toutes les combinaisons de E à p éléments dans l'ordre
def Combinaisons (E,p):
    H=fcar(p,2**len(E))
    H.reverse()
    return [assoc(E,h) for h in H]
 
 
#calcule le nombre d'éléments communs aux listes X,Y
def communs(X,Y):
    n=0;
    for x in X:
        if x in Y:
            n+=1
    return n
 
# liste des éléments à conserver dans T2 selon le critère nombre d'éléments avec L <p
def Conserver(T2,L,q):
    return [X for X in T2 if communs(X,L)<q]
 
#Calcule combien de combinaisons X peut supprimer dans R sur la base de p éléments communs au moins
def PeutSupprimer(X,p):
    global Reste
    H=[L for L in Reste if communs(X,L)>=p]
    return len(H)
 
# détermine la combinaison qui supprime le plus de combinaisons dans T1
def TrouveSuivant(p):
    global Tab1
    s=PeutSupprimer(Tab1[0],p)
    S=Tab1[0]
    for X in Tab1:
        t= PeutSupprimer(X,p)
        if t >s:
            s=t
            S=X
    return S
 
# enleve l'élement X de la liste L
def Enleve(X,L):
    return [Y for Y in L if Y !=X]
 
#trace pour constater l'avancement
def Voir():
    global Reste, Valid,Tab1
    print len(Tab1),len(Reste),Valid[-1]
 
 
# effectue le traitement indiqué
def Traite(p):
    global Reste, Valid,Tab1
    Reste=Conserver(Reste,Tab1[0],5)
    X=[1,2,3,4,5,6];
    Valid.append(X)
    Tab1=Enleve(X,Tab1)# on enlève la première
    while Reste !=[]:
        X=TrouveSuivant(p)
        Reste=Conserver(Reste,X,p)
        Valid.append(X)
        Tab1=Enleve(X,Tab1)
 
#variables globales
Valid=[]
Tab1=[]
Reste=[]
 
def main():
    global Reste,Tab1,Valid
    N=range(1,11)# les nombres de 1 à 10
    Valid=[]
    Tab1=Combinaisons(N,6)
    Reste=Combinaisons(N,6)
    Traite(5)
    print len(Valid)
    print Valid
 
if __name__ == '__main__':
    main()