Système réducteur

freddy · 06-11-2013 21:20:49

Salute a tutti,

je profite que Barbichu ait repointé le bout de son bouc pour relancer un sujet sur lequel on avait un peu séché, et pour cause.

Il s'agit non pas de trouver le nombre minimal de p-grilles à construire à partir de [tex]n \gt p[/tex] nombres de telle sorte qu'on soit sûr qu'un tirage sans remise de p nombres parmi n contiennent [tex]q \lt p[/tex] nombres par des méthodes de dénombrement, mais plutôt de trouver l'algorithme qui répond à la question.

Par exemple, on trouve sur le net un gars qui donne les 36 grilles de l'euromillion à jouer pour être certain qu'à chaque tirage (5 nombres parmi 50 et 2 étoiles parmi 11), on soit certain d'avoir au moins une paire. Ces 36 grilles couvrent toutes les paires possibles.

Dans un autre post, totomn avait donné une réponse similaire à une question de même nature, sans indiquer par contre la méthode utilisée.

Je ne suis pas particulièrement versé en algorithmique, ni d'ailleurs en informatique et serais désireux de comprendre comment il faut s'y prendre pour construire ces grilles.

Dans un ancien numéro de Jeux et Stratégies, la même question avait été posée pour le Loto (6 numéros parmi 49), et il aurait été établi qu'on y arrivait avec moins de 150 grilles.

C'est un peu ce que je souhaiterais arriver à faire, avec l'aide de bons informaticiens - logiciens.

D'avance, merci pour vos contributions !

Dernière modification par freddy (06-11-2013 22:07:06)

freddy · 07-11-2013 12:04:34

Re,

j'ai fait une plus longue recherche sur le Web cette nuit.
Le problème relève de la théorie de l'optimisation combinatoire ... qui n'est pas sans lien avec la théorie des graphes ni avec celle de de la programmation linéaire avec des nombres entiers. En bref, un beau sujet de recherche opérationnelle.

Encore de beaux jours devant moi :-)))

totomm · 08-11-2013 14:07:14

Bonjour,

Etonnant ces 36 grilles : garantissant que toute paire sera dans au moins une grille ?

50 numéros conduisent à 1225 paires possibles
une grille de 5 numéros contient 10 paires, donc 36 en contiendront …
il faut donc que ces grilles soient des grilles multiples …contenant jusqu'à 10 numéros ?

Pour en revenir au problème cité par Freddy :
Forum Programmation Combinaison de 12 nombres, triplets par totomm
Le code est documenté au post #6 et l'algorithme re-expliqué au post #20
Dernière intervention le 16/11/2011 par yoshi

La main passe donc à Barbichu

freddy · 08-11-2013 15:15:33

Re,

une preuve ? Voici !

totomm · 08-11-2013 18:46:26

Bonjour,

Je n'ai jamais pensé qu'on ne pouvait pas créer un système réduit de grille
Mais avec quelle perspective de rentabilité ? d'après les auteurs eux-mêmes ce n'est absolument pas assuré, le contraire est dit avec beaucoup de précautions.

et cette équation pour arriver à 36 ! Vous en connaissez, vous freddy, l'arithmétique ?

freddy · 08-11-2013 19:15:44

Re,

comme on dit, si on veut faire fortune en jouant au casino, il faut acheter le casino !

Mes préoccupations sont plus élevées : je cherche la méthode qui permet de trouver le nombre minimal de 5-grilles et la liste des 5-grilles à jouer pour être certain d'avoir toutes les paires possibles lors de chaque tirage de 5 numéro parmi 50.
Ce n'est pas plus compliqué que cela.
Ma récompence est de trouver, pas de jouer !

yoshi · 09-11-2013 14:48:17

Bonjour,

J'ai repris le programme que j'avais écrit vers la fin de la discussion citée par totomm.
Je l'ai retesté et il m'a donné sur ce cas particulier 33 triplets au lieu de 32.
Je me suis donc efforcé dans un premier temps de comprendre ce que j'avais écrit, pour pouvoir l'adapter à ta situation.
Nombre de 5_combinaisons sur 50 : 2.118.760
Nombre de 2_combinaisons sur 50 : 1225
Nombre de 2_combinaisons sur 5 : 10.
J'ai lancé le prog et j'ai trouvé 153 5_combinaisons retenues pour être sûrs d'avoir une paire...
Le gars arrive à 36 ??!!! Est-il bien sur la même problématique ?

Donc dans un 2e temps, je vais me pencher à nouveau sur le prog et voir pourquoi je tombe sur 33 au lieu de 32 dans ce cas de figure :
http://www.bibmath.net/forums/viewtopic.php?id=4819

J'espère trouver et je relancera i alors le prog pour voir.

@+

[EDIT]Apparemment, totomm, serait arrivé à 11 5_combinaisons et non 32 : nombre obtenu en lançant son prog... Pourtant en relisant les posts je vois bien qu'il est question de 32
Alors mon prog serait-il faux.
Je vais devoir y re-travailler parce que même 2 ans après, en relisant la prose de notre ami, je ne comprends pas plus la philosophie de sa méthode...
Ce qui est expliqué au post #20 de cette même discussion pour être apparemment clair, ne m'en semble pas moins effroyablement compliqué...
Voilà ce que j'ai fait :

#!/usr/bin/env python
# -*- coding: cp1252 -*-

import psyco

psyco.full()

def cree_5combi(ni,nj,nk,nl,nm):

    L=[]

    for i in range(1,ni):

        for j in range(i+1,nj):

            for k in range(j+1,nk):

                for l in range(k+1,nl):

                    for m in range(l+1,nm):                  

                        L.append([i,j,k,l,m])

    return L

def cree_2combi(nk,nl):

    M=[]

    for i in range(nk):

        for j in range(i+1,nl):

            M.append([i,j])

    return M

def cree_Indices():

    Idc=[]

    for i in range(4):

        for j in range(i+1,5):

            Idc.append([i,j])

    return Idc

def eclate_5combinaison(Idc,T):

    L=[]

    for i in range(10):

        m,n=Idc[i]

        L.append([T[m],T[n]])

    return L

n,p=10,5

ni=n-p+2

nj=n-p+3

nk=n-p+4

nl=n-p+5

nm=n-p+6

# Initialisations

C5=cree_5combi(ni,nj,nk,nl,nm)

L250=cree_2combi(nk,nl)

Indices=cree_Indices()

# Traitement

Vues_2,Vues_5=[],[]

for i in range(10,0,-1):  # Nombre de paires maximum communes acceptées

    for combi in C5:      # Passe en revue chacune des 5 combinaisons de la liste C5

        # extrait les 10 paires de 2 parmi 5

        M250=eclate_5combinaison(Indices,combi) # extrait les 10 couples de 2 parmi 5

        diff=0

        # Passe en revue chacune des 10 paires extraites de la 5combi en cours

        for paire in M250:

            # Incrémente le compteur de 1 à chaque paire non déjà enregistrée

            if paire not in Vues_2:

                diff+=1

        # Si le compteur de paires non déjà enregistrées est égal au maximum accepté

        if diff==i:

            # Passe en revue chaque paire extraite plus haut

            for j in range(10):

                # Si la paire n'a pas déjà été enregistrée

                if M250[j] not in Vues_2:

                    # Stockage de la paire

                    Vues_2.append(M250[j])

            # Stockage de la 5combinaison

            Vues_5.append(combi)

            # suppression de la 5combinaison de la liste globale

            del C5[C5.index(combi)]

print len(Vues_5)

print Vues_5

Dernière modification par yoshi (09-11-2013 15:22:47)

yoshi · 10-11-2013 12:22:15

Bonjour,

Les brumes commencent à se dissiper.
Réponse avec les triplets, puisqu'essais faits avec eux
Exemple : avec 12 numéros, de 1 à 12...
Il y a 10 triplets de 3 nombres pris par 5.
On commence par :

for i in range(10,0,-1):

Tant que je n'ai pas 10 triplets (dans l'exemple de freddy 10 paires) différents, je poursuis l'examen des quintuplets.
Le 1er quintuplet examiné est [1,2,3,4,5]
Le 1er quintuplet suivant qui donnera 10 triplets (différents) de [1,2,3,4,5] est [1,2,6,7,8] : il aura fallu 3 changements de nombres pour que cela se produise, soit 45 quintuplets... Le 46e sera le bon.
Mais
en éclatant [1,2,3,4,5] on tombe sur
[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] que l'on a stocké
en éclatant [1,2,6,7,8] on tombe sur
[1, 2, 6], [1, 2, 7], [1, 2, 8], [1, 6, 7], [1, 6, 8], [1, 7, 8], [2, 6, 7], [2, 6, 8], [2, 7, 8], [6, 7, 8] que l'on stocke.

On retire de la liste des quintuplets [1,2,3,4,5] et [1,2,6,7,8].
Si on examine l'état des stocks, on se rend compte que par exemple le triplet [1,3,6] généré par un des quintuplets intermédiaires, n'est pas stocké, en raison de l'exigence de 10 triplets tous différents.
Ce qui nécessitera donc un 2e passage avec une exigence ramenée à 9 triplets différents, et ainsi de suite.
Mon commentaire sur la ligne de départ est donc incorrect, je vais changer "communs" en différents...

Je continue mes investigations...

@+

freddy · 11-11-2013 00:37:38

Salut amigo,

jusque là, je te suis bien. Je réfléchis de mon côté !

totomm · 11-11-2013 11:41:33

Bonjour,

Le programme adapté aux grilles de 5 parmi 50 pour avoir toutes les paires
ne sélectionnera en première passe que (déjà au moins cela) 60 grilles pour n'obtenir que 600 paires sur les 1225.
Et avec un temps de calcul qui devient bien long...

Et si vous vouliez passer à des grilles de 9 ou 10 parmi 50 pour tenter de ne pas dépasser 36 grilles couvrant toutes les paires,
il vous faudra un vraiment gros ordinateur...
Il faut donc chercher un autre algorithme que celui mis en oeuvre pour des grilles de 5 parmi 12

Bonne continuation : totomm

yoshi · 11-11-2013 12:09:55

Bonjour,

On va chercher...
En attendant, voici mon programme épuré avec commentaires modifiés...

#!/usr/bin/env python
# -*- coding: cp1252 -*-

import psyco

psyco.full()

def cree_5combi(ni,nj,nk,nl,nm):

    L=[]

    for i in range(1,ni):

        for j in range(i+1,nj):

            for k in range(j+1,nk):

                for l in range(k+1,nl):

                    for m in range(l+1,nm):                  

                        L.append([i,j,k,l,m])

    return L

def cree_Indices():

    Idc=[]

    for i in range(4):

        for j in range(i+1,5):

            Idc.append([i,j])

    return Idc

def eclate_5combinaison(Idc,T):

    L=[]

    for i in range(10):

        m,n=Idc[i]

        L.append([T[m],T[n]])

    return L

n,p=50,5

ni=n-p+2

nj=n-p+3

nk=n-p+4

nl=n-p+5

nm=n-p+6

# Initialisations

C5=cree_5combi(ni,nj,nk,nl,nm)

Indices=cree_Indices()

# Traitement

Vues_2,Vues_5=[],[]                           

for i in range(10,0,-1):  # 10,9,8,7...1 paires différentes exigées

    for combi in C5:    # Passe en revue chacune des 5 combinaisons de la liste C5

        # extrait les 10 paires de 2 parmi 5 dse chaque combi

        M=eclate_5combinaison(Indices,combi) # extrait les 10 couples de 2 parmi 5

        diff=0

        # Passe en revue chacun des 10 paires extraites de la 5combi en cours

        for paire  in M:

            # Incrémente le compteur de 1 à chaque paire non déjà enregistrée

            if paire not in Vues_2:

                diff+=1

        # Si le compteur de paires non déjà enregistrés est égal au maximum accepté

        if diff==i:

            # Passe en revue chaque paire extraite plus haut et la stocke

            for j in range(10):

                Vues_2.append(M[j])

            # Stockage de la 5combinaison

            Vues_5.append(combi)

            # suppression de la 5combinaison de la liste globale

            del C5[C5.index(combi)]

print len(Vues_5)

print Vues_5

J'ai tout vérifié, dans la version épurée pour combinaisons de 5 parmi 12 et triplets, et je ne vois toujours pas pourquoi totomm avait trouvé 32 quintuplets et moi 33...

@+

totomm · 11-11-2013 15:39:41

Bonjour,

parce que totomm, ayant 33 et constaté un fort déséquilibre dans le nombre d'apparitions des 12 objets, étant maitre de sa programmation,
a ajouté quelques conditions de re-équilibrage (dans son programme) après :
# Essai d'égalisation entre nombres quand k==0
combOK=1
if k==0: # Mettre ici 15 au lieu de 0 entraine 33 5-Combinaisons
. . .

yoshi · 11-11-2013 15:51:45

Bonjour,

Voilà qui me rassure.
Parce que je voyais pas la faille dans ce que j'avais réécrit...

@+

Barbichu · 15-11-2013 23:05:59

Bonjour freddy,
j'ai passé quelques heures à réfléchir au problème et pour l'instant je ne trouve pas mieux que les solutions déjà postée (qui au passage ne donnent pas de garantie sur la minimalité de la solution). Je ne compte pas y réfléchir beaucoup plus car j'ai d'autres chats à fouetter, désolé.
A+

freddy · 16-11-2013 00:29:42

Salut Barbichu,

et merci de ta réponse. Je comprends que c'est un sujet compliqué, c'est un peu ce que je pressentais.
Ne sois pas désolé, et ne perds pas plus de temps. J'ai un tout petit peu progressé de mon côté, je vois bien que c'est une question de longue haleine qui ne répond à aucun besoin pour l'heure.

Merci encore et porte toi bien !

freddy · 29-12-2013 11:32:56

Bonjour,

j'ai un peu poussé le travail sur la recherche du nombre minimal de 5-12 grilles pour trouver toutes les 3-12 grilles. Je me suis aperçu que la procédure de recherche de totomn ne donne pas immédiatement le bon nombre de grilles minimales (32 sauf erreur) car le point de départ de règle de sélection ne conduit pas immédiatement au bon résultat.

Par contre, en prenant un autre point de départ, ou bien en ne retenant pas la première grille logique suivante, on aboutit soit à un nombre plus élevé de grilles, soit au nombre de 32. D'où l'idée de faire une recherche quasi* exhaustive "manuellement" pour être certain de trouver le bon nombre minimal de grilles.

* "Quasi" car il est probable que certains chemins puissent être éliminés assez rapidement.

Faut encore pousser la réflexion ...

freddy · 23-08-2015 11:04:49

Salut,

je reviens sur ce sujet (que je n'ai pas lâché !).

Ce qui manquait à l'analyse de totomm (où est-il passé, le bougre ?) était de vérifier qu'il ne restait que 220 3-combinaisons. Or, plusieurs se répètent, montrant la sous-optimalité.

A la main et sans vraie stratégie logique, je ne suis pas arrivé à faire moins que 32 quintuplets, avec le test des 220 triplets uniques vérifiés. Mais c'est très long, je suis très loin d'avoir tout vu.

La solution actuelle avec 29 quintuplets (qui démarre avec la ligne numéros 33 des quintuplets) donne aussi exactement 220 triplets uniques.

Je pense qu'en balayant avec un automate tous les possibles + le test de 220 triplets uniques devrait permettre d'établir le nombre minimal de quintuplés donnant tous les triplets ,sans omission ni répétition.

Ma seule frustration est de ne pas avoir trouvé la bonne méthode pour calculer ce nombre minimal ... Pas grave, j'ai encore 25 ans pour trouver :-)

camille23 · 24-08-2015 09:48:33

Bonjour,

@freddy pour la bonne méthode :

"The electronic Journal of Combinatorics" adresse :
http://www.combinatorics.org/ojs/index. … w/v19i3p28
où on peut accéder à un .pdf : "Some Constructions of General Covering Designs"
avec bibliographie

Pour rechercher parmi les covering designs
taper sous google "La Jolla Covering Repository"
qui envoie à : https://www.ccrwest.org/cover.html

Pour le set de C(12,5,3)<=29
http://www.ccrwest.org/cover/t_pages/t3 … 2_5_3.html

aussi :
http://www.openproblemgarden.org/op/covering_designs

freddy · 24-08-2015 11:41:08

Salut,
très intéressant, merci beaucoup !

Forum de mathématiques - Bibm@th.net

#1 06-11-2013 21:20:49

Système réducteur

#2 07-11-2013 12:04:34

Re : Système réducteur

#3 08-11-2013 14:07:14

Re : Système réducteur

#4 08-11-2013 15:15:33

Re : Système réducteur

#5 08-11-2013 18:46:26

Re : Système réducteur

#6 08-11-2013 19:15:44

Re : Système réducteur

#7 09-11-2013 14:48:17

Re : Système réducteur

#8 10-11-2013 12:22:15

Re : Système réducteur

#9 11-11-2013 00:37:38

Re : Système réducteur

#10 11-11-2013 11:41:33

Re : Système réducteur

#11 11-11-2013 12:09:55

Re : Système réducteur

#12 11-11-2013 15:39:41

Re : Système réducteur

#13 11-11-2013 15:51:45

Re : Système réducteur

#14 15-11-2013 23:05:59

Re : Système réducteur

#15 16-11-2013 00:29:42

Re : Système réducteur

#16 29-12-2013 11:32:56

Re : Système réducteur

#17 23-08-2015 11:04:49

Re : Système réducteur

#18 24-08-2015 09:48:33

Re : Système réducteur

#19 24-08-2015 11:41:08

Re : Système réducteur

Pied de page des forums