Les systèmes réducteurs [Résolu]

Signaler
Messages postés
4719
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
1 février 2021
-
Messages postés
32
Date d'inscription
samedi 8 mai 2004
Statut
Membre
Dernière intervention
9 février 2010
-
Bonjour à tous,

Autre sujet de mathématiques, mais un tantinet plus attirant que le dernier déposé..
Cela pourrait également faire l'objet d'un source ..pour un bon en maths...
Un système réducteur doit avoir par exemple 3 paramètres ex : sys 12/7 avec garantie 8/6.
ce qui signifie une sélection de 12 numéros en combinaisons de 7 nombres et que si
nous avons 8 bons numéros dans les 12, nous avons l'assurance d'avoir un assemblage comportant au moins 6 bons numéros.
Evidemment les choix de systèmes sont inépuisables..
Si on liste toutes les combinaisons possibles dans l'exemple précité cela donne
C(12,7) = 792 combinaisons.
Mais si on utilise un système réducteur, (c-à-dire, un système avec bcp moins de combin et offrant les mêmes garanties), ce nombre est nettement réduit..
Comment donc écrire un programme avec ces 3 paramètres et afficher la liste des associations possibles d'un système réduit répondant aux conditions choisies ?
Voilà un bon thème sur l'analyse combinatoire qui permetta peut-être à certains d'entre nous de gagner à la française des jeux, voire au PMU !

Bref, l'utile et l'agréable sur DelphiFr

cantador
A voir également:

36 réponses

Messages postés
4
Date d'inscription
mercredi 7 juillet 2004
Statut
Membre
Dernière intervention
28 octobre 2006

Salut à tous !

Histoire de m'insérer dans ce débat je m'intéresse depuis peu à ces fameux systèmes réducteurs. Alors question formalisation mathématique je ne suis pas trop au top mais malgrès tout je crois avoir réussi à pondre un petit prog Delphi qui permet de calculer des systèmes réducteurs.
Ok c'est assez sommaire pour l'instant mais le programme ne demande qu'à évoluer. Pour le moment il lui faut environ une à deux heures pour calculer un système réducteur de 14 chiffres pour un tirage de 6 numéros (genre le loto).
Cependant, il ne demande qu'à évoluer.

Heu par contre j'ai pas encore trouvé comment uploader du code sur ce site. Donc pour le moment je vous le livre brut de béton (armé).  

program Reducteur;


{$APPTYPE CONSOLE}


uses
  SysUtils;


{
  Objectif : programme de calcul de systèmes réducteurs
  Le programme calcule le nombre de combinaisons nécessaires pour
  être sûr d'obtenir n numéros parmis m tirés sur une sélection de p numéros
}


function Combinaison(AValeurMax : Integer; ASelection : Integer) : Integer;
var
  i : Integer;
  p : Integer;
  r : Int64;
begin
  r := 1;
  p := AValeurMax;
  for i := 0 to Pred(ASelection) do begin
    r := p * r;
    Dec(p);
  end;
  p := ASelection;
  for i := 0 to Pred(ASelection) do begin
    r := r div p;
    Dec(p);
  end;
  Result := r;
end;




var
  i : integer;
  j,k,l,m,n,o,p : Integer;
  n1, n2, n3, n4, n5, n6 : Integer;
  nb_numeros_tires : Integer;
  nb_numeros_selectionnes : Integer;
  nb_numeros_objectif : Integer;
  nb_numeros_max : Integer;
  combinaisons : array of array[0..5] of byte;
  nb_combinaisons : Integer;
  selection : array of Integer;
  nb_combinaisons_selectionnee : Integer;
  nb_numero_communs : Integer;
  satisfaisant: Boolean;
  found : Boolean;
begin
  nb_numeros_tires := 6;     // on part de cette base pour le loto
  nb_numeros_max := 49;
  nb_numeros_objectif := 3;
//  for nb_numeros_objectif := 3 to nb_numeros_tires do begin
    for nb_numeros_selectionnes := nb_numeros_tires to nb_numeros_max do begin
      // calcul du nombre de combinaisons possibles
      nb_combinaisons := Combinaison(nb_numeros_selectionnes, nb_numeros_tires);
      SetLength(combinaisons, nb_combinaisons);
      System.Writeln(Format('Selection : %d '#7' Combinaisons : %d', [nb_numeros_selectionnes, nb_combinaisons]));


      // remplissage du tableau
      combinaisons[0][0] := 1;
      combinaisons[0][1] := 2;
      combinaisons[0][2] := 3;
      combinaisons[0][3] := 4;
      combinaisons[0][4] := 5;
      combinaisons[0][5] := 6;
      if High(Combinaisons) > 0 then begin
        for i := 1 to High(Combinaisons) do begin
          for j := 0 to High(Combinaisons[i]) do begin
            Combinaisons[i][j] := Combinaisons[i-1][j];
          end;
          j := High(Combinaisons[i]);
          Inc(Combinaisons[i][j]);
          while Combinaisons[i][j] > (nb_numeros_selectionnes + j - High(Combinaisons[i])) do begin
            Inc(Combinaisons[i][j-1]);
            Dec(j);
          end;
          for j := 1 to High(Combinaisons[i]) do begin
            if Combinaisons[i][j] > (nb_numeros_selectionnes + j - High(Combinaisons[i])) then begin
              Combinaisons[i][j] := Combinaisons[i][j-1] + 1;
            end;
          end;
        end;
      end;


      // Selection du nombre de combinaisons
      // On Selectionne de 1 à nb_combinaisons


      for i := 1 to nb_combinaisons do begin
        SetLength(selection, i);
        // Selection initiale de combinaisons
        for j := 0 to Pred(i) do begin
          selection[j] := j;
        end;


        satisfaisant := false;
        // On teste toutes les combinaisons possibles de combinaisons
        for j := 0 to Pred(Combinaison(nb_combinaisons, i)) do begin
          p := High(selection);
          while selection[p] > High(Combinaisons) + p - High(Selection) do begin
            Inc(selection[p-1]);
            dec(p);
          end;
          for p := 1 to High(selection) do begin
            if selection[p] > High(Combinaisons) + p - High(Selection) then begin
              selection[p] := selection[p-1] + 1;
            end;
          end;


          // Test effectue pour chacune des combinaisons possibles
          for k := 0 to High(Combinaisons) do begin


            // On cherche si au moins un de nos combinaisons
            // statisfait la contrainte
            found := False;
            for l := 0 to High(selection) do begin
              nb_numero_communs := 0;
              for m := 0 to High(Combinaisons[k]) do begin
                for n := 0 to High(Combinaisons[selection[l]]) do begin
                  if Combinaisons[k][m] = Combinaisons[selection[l]][n] then begin
                    Inc(nb_numero_communs);
                    if nb_numero_communs = nb_numeros_objectif then break;
                  end;
                end;
                if nb_numero_communs = nb_numeros_objectif then break;
              end;              found :nb_numero_communs nb_numeros_objectif;
              if found then break;
            end;
            if not found then begin
              satisfaisant := False;
              break;
            end else begin
              satisfaisant := True;
            end;
          end;


          // On a testé notre ensemble de combinaisons, si ce dernier n'est pas
          // satisfaisant, on en change
          if not satisfaisant then begin
            Inc(Selection[High(Selection)]);
          end else begin
            Writeln(Format('%d combinaisons necessaires', [Length(Selection)]));
            for k := 0 to High(selection) do begin
              for l := 0 to High(Combinaisons[selection[k]]) do begin
                write(Format('%.2d ', [combinaisons[selection[k]][l]]));
              end;
              writeln('');
            end;
            break;
          end;
        end;
        if satisfaisant then break;
      end;


    end;
//  end;
  system.Readln;


 


end.
Messages postés
4
Date d'inscription
mercredi 7 juillet 2004
Statut
Membre
Dernière intervention
28 octobre 2006

Oui je sais et c'est tout le problème : trouver des astuces de codes permettant d'accélérer le traitement mais également confronter les résultats à l'ensemble des tirages possibles.
Je pense qu'une première optimisation pourrait simplement consister à dire que si pour une sélection de n numéros le système réduit est constitué de p grilles, alors pour n+1 numéro le système réduit sera constitué d'au moins p grilles égalements. Je ne pense prendre de grands risques en proposant ce postulat. C'est pas grand chose à modifier dans le programme mais je crois que cela peut permettre d'éconimiser pas mal de temps.
Maintenant, il ne faut réver non plus, si tu regardes bien sur le net tu verra que certains ont créés des clusters de calculs de systèmes réduits.
Autre axe d'amélioration du programme de base :
A priori, pour une sélection de n numéros on peut trouver plusieurs systèmes réduits. Exemple pour une sélection de 7 chiffre le système réduit 1-2-3-4-5-6 fonctionne mais également 2-3-4-5-6-7 (il doit y en avoir 7 au total).
Bon là c'est un cas simple mais pour des systèmes plus complexe je me demande si la couverture de combinaisons est identique. Je veux dire par là que bien sûr on est sûr d'avoir au moins 3 numéros gagnants mais qu'en est-il des combinaions de 4 5 voire 6 numéros.
6 numéros c'est facile, on en couvre autant que l'on sélectionne de grilles. Mais couvre-t-on autant de de combinaisons de 3 et 4 chiffres dans chaque système réduit ?
Tu noteras que le programme proposé ne permet que de trouver un seul système réduit. (et c'est déjà bien assez long comme ça).
Messages postés
4
Date d'inscription
mercredi 7 juillet 2004
Statut
Membre
Dernière intervention
28 octobre 2006

Tiens en zyeutant à droite à gauche sur le net, je crois que j'ai trouvé peut être une piste d'amélioration du système de calcul. En fait on doit pouvoir faire beaucoup plus rapide en prenant le problème à l'envers : plutôt que de rechercher les combinaisons qui permettent de résoudre le problème comme ça brutalement ne serait-il pas mieux de chercher parmis les n combinaisons possibles celles qui ont moins de 3 numéros en commun ; du coup on fait un seul passage sur l'ensemble des combinaisons et on vérifie à la fin que l'on a ce que l'on a bien ce que l'on voulait.
Euh tu m'as suivi ?

Bon je vais essayer de recoder ça et je te transmet le bout de code.

A+

Despeludo
Messages postés
4
Date d'inscription
mercredi 7 juillet 2004
Statut
Membre
Dernière intervention
28 octobre 2006

Ok effectivement c'est beaucoup plus rapide.
J'ai obtenu un système réduit pour un sélection de 6 à 49 numéros en moins de dix minutes.
Par contre je n'ai mis la vérification  pour gagner du temps. Libre à toi de le faire.
Alors comme promis je remets le code ici.
Bon courage pour les prochains tirages.

=========================================================

program Reducteur;


{$APPTYPE CONSOLE}


uses
  SysUtils;


{
  Objectif : programme de calcul de systèmes réducteurs
  Le programme calcule le nombre de combinaisons nécessaires pour
  être sûr d'obtenir n numéros parmis m tirés sur une sélection de p numéros
}


type
  TCombinaison = record
    Necessaire : Boolean;
    Tirage : array[0..5] of byte;
  end;




function Combinaison(AValeurMax : Integer; ASelection : Integer) : Integer;
var
  i : Integer;
  p : Integer;
  r : Int64;
begin
  r := 1;
  p := AValeurMax;
  for i := 0 to Pred(ASelection) do begin
    r := p * r;
    Dec(p);
  end;
  p := ASelection;
  for i := 0 to Pred(ASelection) do begin
    r := r div p;
    Dec(p);
  end;
  Result := r;
end;




var
  i : integer;
  j,k,l : Integer;
  nb_numeros_tires : Integer;
  nb_numeros_selectionnes : Integer;
  nb_numeros_objectif : Integer;
  nb_numeros_max : Integer;
  combinaisons : array of TCombinaison;
  nb_combinaisons : Integer;
  nb_numero_communs : Integer;
  nb_combinaisons_selectionnee : Integer;
begin
  nb_numeros_tires := 6;     // on part de cette base pour le loto
  nb_numeros_max := 49;
  nb_numeros_objectif := 3;
  for nb_numeros_selectionnes := nb_numeros_tires to nb_numeros_max do begin
    // calcul du nombre de combinaisons possibles
    nb_combinaisons := Combinaison(nb_numeros_selectionnes, nb_numeros_tires);
    SetLength(combinaisons, nb_combinaisons);
    System.Writeln(Format('Selection : %d '#7' Combinaisons : %d', [nb_numeros_selectionnes, nb_combinaisons]));


    // remplissage du tableau
    combinaisons[0].Tirage[0] := 1;
    combinaisons[0].Tirage[1] := 2;
    combinaisons[0].Tirage[2] := 3;
    combinaisons[0].Tirage[3] := 4;
    combinaisons[0].Tirage[4] := 5;
    combinaisons[0].Tirage[5] := 6;
    Combinaisons[0].Necessaire := True;   // Par défaut on garde tout
    if High(Combinaisons) > 0 then begin
      for i := 1 to High(Combinaisons) do begin
        for j := 0 to High(Combinaisons[i].Tirage) do begin
          Combinaisons[i].Tirage[j] := Combinaisons[i-1].Tirage[j];
        end;
        j := High(Combinaisons[i].Tirage);
        Inc(Combinaisons[i].Tirage[j]);
        while Combinaisons[i].Tirage[j] > (nb_numeros_selectionnes + j - High(Combinaisons[i].Tirage)) do begin
          Inc(Combinaisons[i].Tirage[j-1]);
          Dec(j);
        end;
        for j := 1 to High(Combinaisons[i].Tirage) do begin
          if Combinaisons[i].Tirage[j] > (nb_numeros_selectionnes + j - High(Combinaisons[i].Tirage)) then begin
            Combinaisons[i].Tirage[j] := Combinaisons[i].Tirage[j-1] + 1;
          end;
        end;
        Combinaisons[i].Necessaire := True;
      end;
    end;


    // Recherche des combinaisons nécessaires
    nb_combinaisons_selectionnee := 0;
    for i := 0 to Pred(nb_combinaisons) do begin
      if Combinaisons[i].Necessaire then begin
        Inc(nb_combinaisons_selectionnee);
        for j := i + 1 to Pred(nb_combinaisons) do begin
          nb_numero_communs := 0;
          for k := 0 to High(Combinaisons[i].Tirage) do begin
            for l := 0 to High(Combinaisons[j].Tirage) do begin
              if Combinaisons[i].Tirage[k] = Combinaisons[j].Tirage[l] then begin
                Inc(nb_numero_communs);
                if nb_numero_communs = nb_numeros_objectif then break;
              end;
            end;
            if nb_numero_communs = nb_numeros_objectif then break;
          end;
          if nb_numero_communs = nb_numeros_objectif then begin
            Combinaisons[j].Necessaire := False;
          end;
        end;
      end;
    end;


    // Affichage
    Writeln(Format('%d combinaisons necessaires', [nb_combinaisons_selectionnee]));
    for i := 0 to Pred(nb_combinaisons) do begin
      if Combinaisons[i].Necessaire then begin
        for j := 0 to High(Combinaisons[i].Tirage) do begin
          write(Format('%.2d ', [Combinaisons[i].Tirage[j]]));
        end;
        writeln('');
      end;
    end;


  end;
  system.Readln;


end.
Messages postés
4719
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
1 février 2021
14
Je ne pense qu'il soit utile de tester toutes les sélections car qd on joue on sélectionne une série de numéros et ensuite on choisit un type de grille.
Par ailleurs, on doit pouvoir choisir son jeu..(loto, keno, pmu + ceux à l"étranger
et il y en a bcp..)
ce qui revient à dire que la poblématique est la suivante :

Combien (et comment) faut-il prendre au minimum de p-parties (les grilles)  de {1,...,m} (la sélection) pour que toute t-partie  de {1,...,m}  (trace du tirage dans la sélection) ait au moins r éléments communs (combinaison gagnante) avec au moins l’une d’entre elles?

Car en fait, ce qui compte c'est de jouer le minimum de combinaisons permettant d'assurer à X % (pour l'instant à 100 %, mais après c'est à étudier)
c'est-à-dire être certain d'avoir la condition de garantie que l'on a choisit au départ et au moins UNE FOIS.
Ex : tu prend 15 numéros, jouer des grilles de 6 et tu veux une garantie de 5/7 et c'est-à-dire avoir au moins une grille de 5 bons numéros sur 6 si 7 bons numéros sortent dans les 15.
Quelles sont les combinaisons minimum à jouer(bien sûr afin de dépenser le moins possible)
afin d'assurer le résultat escompté ?

et c'est pas sûr qu'il n'y ait qu'une solution..



Enfin, ça commence à chauffer et çà devient très intéressant..


Evidemment, reste le problème du choix de la sélection, mais ça c'est un autre débat...



Je propose que tu déposes ton programme sur le forum en créant une interface + une ListBox1 + Tbutton1 + placer 3 edits et remplacer les writeln par ListBox1.items.add(Format(....));
pour le 2e writeln, il suffit de faire une concaténation..

Ce qui permettra d'avoir un ensemble plus convivial et d'élargir le débat à tout le forum.

@+
 
cantador
Messages postés
6
Date d'inscription
mercredi 1 octobre 2008
Statut
Membre
Dernière intervention
3 octobre 2008

Bonjour à tous !
Voilà, je suis tout nouveau et je n'y connais rien de rien en math. Mais, je suis amateur de Kéno. Je viens de m'inscrire sur le site car j'ai remarqué que vous en parliez (mais vous êtes tous de gros connaisseurs). Quant à moi, je suis le joueur lambda de tous les jours. J'ai une question, en espérant que l'on puisse m'apporter une aide.
Voilà, j'ai 19 n° fétiches. Je désire jouer des grilles de 6 n° (potentiel de gains pour 6 bons n° 1000€, pour 5n° 30€ et 4n° 2€....mais je ne vous apprends rien). J'aimerais savoir si un système réducteur existe pour jouer 19n° et être certain d'obtenir les 6 bons numéros, si 6/7/8 ou 9n° ... sortent dans ma selection de 19n°. J'espère que mes explications sont assez claires pour avoir une réponse de votre part. (Moi, je me comprends, mais je ne suis pas sûr d'être bien clair, veuillez m'en excuser SVP, merci). J'attends avec impatience vos réponses.
Cordialement à tous ! et encore merci d'avance !
Hallyd
Messages postés
6
Date d'inscription
mercredi 1 octobre 2008
Statut
Membre
Dernière intervention
3 octobre 2008

Pardon, je pense que 6 bons n° sur 19, c'est beaucoup trop (après réflexion). Par contre est-ce que vous pouvez me dire si cela est possible avec 9 numéros. Donc un système efficace de 6/6 bon numéros sur 9 joués. Bien sûr, si 6n° sont corrects dans ma sélection. Merci et à bientôt. Hallyd
Messages postés
4719
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
1 février 2021
14
bonsoir,

Si ta sélection est de 19 numéros, il est inutile de tenter de gagner une grille de 6/6, le nombre de combinaisons a joué étant trop important.

en revanche tu peux jouer des grilles de 10 avec une petite chance de gagner
(si tu as 9 bons numéros/19) une grille de 6/10 ou 7/10.
les autres gains sont hors de portée..
je sais c'est dur, mais c'est la dure réalité.

cantador
Messages postés
6
Date d'inscription
mercredi 1 octobre 2008
Statut
Membre
Dernière intervention
3 octobre 2008

 Bonsoir,
Merci mille fois Cantador, et dis moi. 6/9 d'après toi c'est faisable ?
merci
Messages postés
4719
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
1 février 2021
14
Oui, des grilles de 6/6(1000€), 6/7, 6/8, 6/9 sont possibles.
En fait toute la difficulté est d'avoir une sélection riche la plus courte possible.
il faut beaucoup d'observation(ou faire un programme qui le fait automatiquement) et aussi de la chance.

cantador
Messages postés
6
Date d'inscription
mercredi 1 octobre 2008
Statut
Membre
Dernière intervention
3 octobre 2008

Superbe Cantador, merci !
Mais maintenant, comment je fais. Est-ce que tu peux me mettre la
solution.......mais pas comme vous faites avec tel ou tel formule, car
je n'y comprends absolument rien, vous êtes tous trop 'balaises'.
Est-ce que tu m'alligner les nombres, que j'y comprenne quelque chose.
Peux-tu me faire ca ? ou est-ce trop demandé, car trop long !
Merci, j'attends ta réponse. Cordialement
Messages postés
4719
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
1 février 2021
14
hou là, il n'existe pas de solutions miracles...
mais à force d'observations, on finit par écrire un programme qui note certaines choses..et de temps en temps ça marche..mais si on fait la somme des gains et des pertes, ca reste faiblard...
C'est surtout un passe-temps comme un autre..
Mais n'espère pas t'enrichir..sauf un coup de bol de gagner un gros lot.
et ensuite tu vas à la pêche ou à la chasse !
cantador
Messages postés
6
Date d'inscription
mercredi 1 octobre 2008
Statut
Membre
Dernière intervention
3 octobre 2008

Ah ok, merci !
Je pensais que tu pourrais me donner le système réducteur de 6/6 pour 9 n° choisis.
Tout comme les 4 combinaisons au lieu des 28 pour 8n° choisis (cité quelques pages plus haut).
Bon, tant pis, merci quand même et à bientôt, j'espère !
Messages postés
4719
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
1 février 2021
14
tu n'as pas bien lu...


tu les as :


01 02 03 04 05 06
01 02 03 04 07 08
01 02 05 06 07 08
03 04 05 06 07 08

il suffit de remplacer les numéros (1 à 8) par leurs valeurs !


Quant aux systèmes réducteurs pour des sélections plus importantes, il suffit de chercher sur le net..et tu en trouveras..

cantador
Messages postés
6
Date d'inscription
mercredi 1 octobre 2008
Statut
Membre
Dernière intervention
3 octobre 2008

Super Cantador, je te remercie !
Cordialement
Messages postés
32
Date d'inscription
samedi 8 mai 2004
Statut
Membre
Dernière intervention
9 février 2010

Les Systemes reducteurs, un domaine interressant.
Dans le feu magasine Jeux et Strategie, il y  eut un exercice de ce style sur le Loto.
C'etait , combien de grilles de loto ( de 6 num)  faut'il jouer pour etre certain d'en avoir au moins 1 gagnante, c'est a dire qui comporte au moins 3 bons numeros.

Le Systeme de l'epoque donnait 175 grilles,  optimisé à 174 peu apres.

L'article detaillait la methode employé pour obtenir ce resultat .
Le probleme etait "un casse tete de rangement".

ATitus_[8D]