combinaisons de p éléments parmi n

Version imprimable

15/06/2012, 13h53
Invité

combinaisons de p éléments parmi n

bonjour

besoin d'une aide, je ne sais pas faire etje suis débutant
je souhaiterai avoir un programme qui permet d'avoir de toutes les combinaisons possibles d'un tirage exemple : [ABCD]
je veux [AB] [AC] [AD] [BC] [BD] [CD]
et aussi je voudrai paramtrer les elements dans ces tirages
exêmple[ABC] [ABD] [BDC]

pouvez vous m'aider

Si j'ai bien compris ce que tu veux faire, je pense que le plus simple pour toi est d'utiliser une fonction récursive (après on pourra toujours optimiser) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
fonction x(const std::string & prefixe,const std::string & MesCaractères)
{
        //si MesCaractères n'a qu'un seul élement :
                std::cout << prefixe << MesCaractères << std::endl;
        //sinon
                //pour chaque élément de MesCaractères
                          std::string prefixeTmp = prefixe;
                          prefixeTmp += MesCaractères[i];
                          MesCaractèresTmp = MesCaractères;
                          //on retire le ième élément de MesCaractèresTmp.
                          x(prefixeTmp, MesCaractèresTmp);
}

Je t'ai un peu maché le travail, donc essaye de refaire ceci mais avec une itérative^^

15/06/2012, 15h03
Invité

je m'en sors pas
jarrive pas a activer cette fonction
peux tu me donner un exemple

En fait il vaut mieux utiliser un prototype du style :

Code:

1
2
 
void combinaison(const std::string & MesCaractères, const std::string & prefixe = "");

Pour l'utiliser, c'est très simple :

Code:

1
2
 
combinaison("ABCDEFGHIJKLMNOP");/* /!\ si tu veux que des combinaisons soit rangée dans l'ordre alphabétique et qu'il n'y ai pas de doublon, il fait que la chaine de départ soit rangée dans l'ordre alphabétique sans doublons. */

15/06/2012, 16h44
Invité

et bien je n y 'arrive
je ne comprends pas comment mettre bout à bout le programme pour qul fonctionne
je suis un boulet
desole
15/06/2012, 16h52
Neckara

Montre moi ce que tu as déjà fait.

N'oublie pas :
:tagcode:
(Depuis le temps que j'ai envie d'essayer ce smiley^^)

Citation:

Envoyé par fabrice192

et bien je n y 'arrive
je ne comprends pas comment mettre bout à bout le programme pour qul fonctionne
je suis un boulet
desole

Il n'y a rien de boulet à souhaiter comprendre.

Apparemment, tu ignores comment réaliser un programme complet.
Voici la structure d'un programme court en C++:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /* inclusions des en-têtes utilisés, par exemple: */ #include <string> //... /* déclarations des fonctions, normalement, dans un fichier d'en-tête séparé: */ void combinaison(const std::string & MesCaractères, const std::string & prefixe = ""); /* la fonction main, point de départ du programme*/ int main(){ // ou int main( int nbArguments, char** arguments) { //... combinaison("ABCDEFGHIJKLMNOP"); /* /!\ si tu veux que des combinaisons soit rangée dans l'ordre alphabétique et qu'il n'y ai pas de doublon, il fait que la chaine de départ soit rangée dans l'ordre alphabétique sans doublons. */ //... return 0;//un retour 0 pour signaler un arret normal du programme } /* définitions des fonctions ayant leurs prototypes (normalement dans un autre fichier source, lié à la compilation */ void combinaison(const std::string & MesCaractères, const std::string & prefixe){ // ici le code }
Ceci ne résoudra pas tout ton problème (qui ressemble beaucoup à un bon exercice d'étudiant), mais ca devrait te débloquer.
Je te recommande de lire la faq C++ de notre cher site

PS: Définir d'autres fonctions que main dans le fichier principal est souvent une entrave à la lisibilité.

19/06/2012, 13h08
oodini

Récupérer la formule de maths sur les combinaisons, et chercher sur le web un algorithme de factorielles (ce qui devrait être facile...).

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
#include	<iostream>
 
void            comb(std::string &a, std::string &b, unsigned int c)
{
  char	bak;
 
  if (b.size() < c)
    {
      for (unsigned int i(0) ; i < a.size() ; ++i)
        {
          if (a[i] != -1)
            {
              b += a[i];
              bak = a[i];
              a[i] = -1;
              comb(a, b, c);
	      a[i] = bak;
              b.erase(b.end() - 1);
            }
        }
    }
  else
    {
      std::cout << "[" << b << "]" << std::endl;
    }
}
 
int     main()
{
  std::string   letters("ABCDEF");
  std::string   result;
 
  comb(letters, result, 2);
  comb(letters, result, 3);
  return (0);
}

Ce code fait ce que tu veut, les résultat ne contienne pas de doublons de lettre (a condition qu'il n'y en ai pas dans la chaîne de départ).

Le resultat:

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
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
151
152
 
 
[AB]
[AC]
[AD]
[AE]
[AF]
[BA]
[BC]
[BD]
[BE]
[BF]
[CA]
[CB]
[CD]
[CE]
[CF]
[DA]
[DB]
[DC]
[DE]
[DF]
[EA]
[EB]
[EC]
[ED]
[EF]
[FA]
[FB]
[FC]
[FD]
[FE]
[ABC]
[ABD]
[ABE]
[ABF]
[ACB]
[ACD]
[ACE]
[ACF]
[ADB]
[ADC]
[ADE]
[ADF]
[AEB]
[AEC]
[AED]
[AEF]
[AFB]
[AFC]
[AFD]
[AFE]
[BAC]
[BAD]
[BAE]
[BAF]
[BCA]
[BCD]
[BCE]
[BCF]
[BDA]
[BDC]
[BDE]
[BDF]
[BEA]
[BEC]
[BED]
[BEF]
[BFA]
[BFC]
[BFD]
[BFE]
[CAB]
[CAD]
[CAE]
[CAF]
[CBA]
[CBD]
[CBE]
[CBF]
[CDA]
[CDB]
[CDE]
[CDF]
[CEA]
[CEB]
[CED]
[CEF]
[CFA]
[CFB]
[CFD]
[CFE]
[DAB]
[DAC]
[DAE]
[DAF]
[DBA]
[DBC]
[DBE]
[DBF]
[DCA]
[DCB]
[DCE]
[DCF]
[DEA]
[DEB]
[DEC]
[DEF]
[DFA]
[DFB]
[DFC]
[DFE]
[EAB]
[EAC]
[EAD]
[EAF]
[EBA]
[EBC]
[EBD]
[EBF]
[ECA]
[ECB]
[ECD]
[ECF]
[EDA]
[EDB]
[EDC]
[EDF]
[EFA]
[EFB]
[EFC]
[EFD]
[FAB]
[FAC]
[FAD]
[FAE]
[FBA]
[FBC]
[FBD]
[FBE]
[FCA]
[FCB]
[FCD]
[FCE]
[FDA]
[FDB]
[FDC]
[FDE]
[FEA]
[FEB]
[FEC]
[FED]

30/06/2012, 10h07
Invité

Les combinaisons n'ordonnent pas les éléments.
[ABC] est égal à [CBA]

edit: cela dit, je sais pas si c'est la peine de suer, l'auteur à l'air d'etre un fantome

@gheaeckkseqrz : si tu veux afficher tous les arrangements possibles, deux simples boucles suffisent :
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 int tailleMin = x; int tailleMax = y; char caractères[] = "..."; int nbCaractère = strlen(caractères); char resultat[y+1] = {0}; char numero[y+1] = {0}; for(int i=0; i != tailleMin - 1; ++i) { resultat[i] = caractère[0]; numero[i] = 1; } for(int i=0; i != ....; ++i) { bool retenue = true; for(int j = 0; retenue; ++j) { if( numero[j]++ == nbCaractères ) numero[j] = 1; else retenue = false; resultat[j] = caractère[numero[j] - 1]; } //affichage/ajout du résultat à la liste }
EDIT : je viens juste d'y penser, mais pour les combinaisons, il suffit juste de modifier le comportement lorsqu'on a une retenue...
C'est assez simple :
- numero[j] doit toujours être encadré de cette manière : numero[j+1] < numero[j] < numero[j-1]

De là on peut en déduire quelques règles :
- numero[j] >= strlen(resultat) - j
- numero[j] <= nbCaractères - j

pour l'exercice matinal les combinaisons

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
 
#include <iostream>
void getOrderedLists(const std::string &s, size_t i, std::string result){
  //complete hand
  for(size_t beg=0; beg<s.size(); ++beg){
    //found hand
    if(i==1){
      std::cout<<"["<<result+s[beg]<<"]"<<std::endl;
      continue;
    }
    //no enough item to pick up to complete hand
    if(s.size()-beg<i){
      return;
    }
    getOrderedLists(s.substr(beg+1), i-1, result+s[beg]);
  }
}
void binomialList(std::string s){
  //size of picked up hand
  for(size_t i=1; i<=s.size(); ++i){
    //just have to pick any ordered list of size i
    getOrderedLists(s, i, "");
  }
}
int main(int argc, char* argv[]){
  binomialList("ABCDE");
}