Plusieurs tirages de couples sans doublons

Version imprimable

13/08/2013, 07h52
cedni

Plusieurs tirages de couples sans doublons

Salut

J ai une liste d"équipes .
Chaque équipe va disputer 5 matchs sans rencontrer 2 fois le même adversaire .

Résoudre ce probléme n est pas si compliqué , pourtant dans certains cas et surtout lorsque la liste d'équipes est petite , un mauvais tirage surgit , il me reste un doublon qui se sont déjà rencontrés .

Je pourrais ne pas valider le tirage et le recommencer , mais je pense que vous connaissez les caprices du random .

N'y aurait-il pas une astuce ?
13/08/2013, 10h58
ShaiLeTroll

Utilise RandomFrom comme dans ma fonction RandomFromExclude dans le random non répétitif
Elle retire du tableau les valeurs déjà tirés et le renvoi comme résultat

Une autre approche est de mémoriser les valeurs déjà tirées, je ne retrouve pas le sujet où l'on avait évoqué, idem une fonction Delphi prête à l'emploi

Sinon, c'est juste un problème de combinatoire, tu veux une "Permutation sans répétition", il y a plein de sujet Delphi qui traite de cela !
13/08/2013, 13h14
cedni

Citation:

Envoyé par ShaiLeTroll

Utilise RandomFrom
Une autre approche est de mémoriser les valeurs déjà tirées, je ne retrouve pas le sujet où l'on avait évoqué, idem une fonction Delphi prête à l'emploi

C est ce que je fais avec randomrange en décrémentant la valeur haute de 2 .
Mais je ne veux pas obtenir l ensemble des tirages , 60 équipes , çà me donnerait un factoriel 60 , c est beaucoup trop long , en sachant que derrière je dois encore tester la validité de la ligne en prenant en compte 1vs2 et 2vs1

Si vous avez d autres idées , je suis preneur

1 bouton , 3 memo
h

Code:

1
2
3
4
 
public:		// Déclarations de l'utilisateur
void __fastcall TForm1::Tirer(int choix);
void __fastcall TForm1::Verif();

cpp

Code:

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
 
TStringList *Equipes  = new TStringList()  ;
TStringList *Tirages  = new TStringList()  ;
TStringList *Test     = new TStringList()  ;
int TirageOk = 0;
int nb ;
int nbEquipes =  12 ;
 
 
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
for ( int i = 1 ; i <=5 ; i++ )
{
Memo1->Lines->Add("-------") ;
TirageOk = 0;
nb = 0;
while ( TirageOk < nbEquipes/2   )
           {
           nb++;
           Test->Clear();
           Tirer(2);
           Verif();
           }
 
Memo3->Lines->Add("good : Tirage "+IntToStr(i)+" Essai "+IntToStr(nb)+" "+IntToStr(TirageOk));
for ( int i =0 ; i< Test->Count ;i++ )
         {
         Tirages->Add(Test->Strings[i]);
         Memo1->Lines->Add(Test->Strings[i]);
         }
}
 
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Tirer(int choix)
{
for ( int i =1 ; i<=nbEquipes ;i++ )  Equipes->Add(i);
while ( Equipes->Count > 0 )
           {
           int k =1;
           // si plus de deux equipes , random entre 1 et count sinon reste à 1
           if ( Equipes->Count  >  2 ) {  k = RandomRange(1,Equipes->Count-1); }
 
                 AnsiString temp  = "E_";
                            temp += Equipes->Strings[0];
                            temp += "_vs_E_";
                            temp += Equipes->Strings[k] ;
                 Equipes->Delete(k);
                 Equipes->Delete(0);
                 Test->Add(temp);
                 }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Verif()
{
TirageOk = nbEquipes /2;
 
for ( int i =0 ; i< Test->Count    ;i++ )
for ( int j =0 ; j< Tirages->Count ;j++ )
if  ( Test->Strings[i] == Tirages->Strings[j]  )
      {
      TirageOk-- ;
      Memo2->Lines->Add(TirageOk);
      Memo2->Lines->Add(Test->Strings[i]+"   "+Tirages->Strings[j]);
      }
}
//---------------------------------------------------------------------------

Salut cedni, voici un bout de code qui pourrait t'aider.

D'abord on ajoute les includes:

Code:

1
2
3
4
#include <algorithm>    // std::random_shuffle
#include <vector>       // std::vector
#include <map>          // std::map
#include <ctime>        // std::time

Ensuite tu peux mettre ce bout de code dans un évènement OnClick de bouton:

Code:

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
std::vector<int> EquipeVector;
for(int i = 1; i <= nbEquipes; ++i)
{   // On ajoute tous les numéros d'équipe dans un vecteur
    EquipeVector.push_back(i);
}
 
std::srand(unsigned(std::time(0))); // Randomize
 
// Une map qui contient une équipe ainsi que ces cinq adversaires
std::map< int, std::vector<int> > EquipeAdversaire;
 
for(int EquipeCourante = 1; EquipeCourante <= nbEquipes; ++EquipeCourante)
{
    // On mélange le tout
    std::random_shuffle(EquipeVector.begin(), EquipeVector.end());
 
    // On va itérer les équipes pour trouver nos cinq adversaires
    for(std::vector<int>::iterator EquipeVectorIt = EquipeVector.begin();
        EquipeVectorIt != EquipeVector.end(); ++EquipeVectorIt)
    {
        if(EquipeAdversaire[EquipeCourante].size() >=5)
        {   // On a déjà nos 5 adversaires
            EquipeVector.erase(std::find(EquipeVector.begin(), EquipeVector.end(), EquipeCourante));
            break;
        }
 
        const int AdversairePotentiel = *EquipeVectorIt;
 
        if(EquipeCourante == AdversairePotentiel)
        {   // On ne peut pas jouer contre soi-même
            continue;
        }
        if(std::find(EquipeAdversaire[AdversairePotentiel].begin(),
            EquipeAdversaire[AdversairePotentiel].end(), EquipeCourante) !=
            EquipeAdversaire[AdversairePotentiel].end())
        {   // On a déjà jouer contre cet adversaire
            continue;
        }
 
        if(EquipeAdversaire[AdversairePotentiel].size() < 5)
        {   // Notre adversaire potentiel n'a pas cinq parties, on peut donc jouer contre lui
            EquipeAdversaire[EquipeCourante].push_back(AdversairePotentiel);
            EquipeAdversaire[AdversairePotentiel].push_back(EquipeCourante);
        }
    }
}
 
// -- Code pour tester débute ici --
Memo1->Lines->Clear();
int Count = 0;
Memo1->Lines->BeginUpdate();
for(std::map< int, std::vector<int> >::iterator EquipeIt=EquipeAdversaire.begin(); EquipeIt!=EquipeAdversaire.end(); ++EquipeIt)
{
    for(std::vector<int>::iterator AdversaireIt=EquipeIt->second.begin(); AdversaireIt!=EquipeIt->second.end(); ++AdversaireIt)
    {
         AnsiString temp  = String(++Count) + ": E_";
                    temp += EquipeIt->first;
                    temp += "_vs_E_";
                    temp += *AdversaireIt;
         Memo1->Lines->Add(temp);
    }
    Memo1->Lines->Add("--------------") ;
}
Memo1->Lines->EndUpdate();
if(Count < (nbEquipes * 5))
{
    MessageDlg(String("Il faut générer encore, il manque des parties à jouer! Il faudrait peut-être appellé la méthode de façon récursive."), mtInformation, TMsgDlgButtons() << mbOK, 0);
}
// -- Code pour tester fini ici --

Il va te falloir un TMemo et définir une valeur à nbEquipes.

Il est très tard il se pourrait que j'ai fait des conneries ;)

22/08/2013, 14h01
cedni

merci je garde çà sous le coude même si mon code fonctionne