Générer des combinaisons en c ++

J’ai recherché un code source pour générer une combinaison en utilisant c ++. J’ai trouvé des codes avancés pour cela mais cela ne convient que pour des données spécifiques à un nombre spécifique. Quelqu’un peut-il me donner des conseils, ou peut-être une idée pour générer une combinaison. A titre d’exemple, supposons que l’ensemble S = {1, 2, 3, …., n} et nous en prenons r = 2. L’entrée serait n et r . Dans ce cas, le programme va générer des tableaux de longueur deux, comme 5 2 sorties 1 2, 1 3, etc. J’ai eu du mal à construire l’algorithme. Cela m’a pris un mois à réfléchir à cela.

    Un moyen simple d’utiliser std::next_permutation :

     #include  #include  #include  int main() { int n, r; std::cin >> n; std::cin >> r; std::vector v(n); std::fill(v.end() - r, v.end(), true); do { for (int i = 0; i < n; ++i) { if (v[i]) { std::cout << (i + 1) << " "; } } std::cout << "\n"; } while (std::next_permutation(v.begin(), v.end())); return 0; } 

    ou une légère variation qui produit les résultats dans un ordre plus facile à suivre:

     #include  #include  #include  int main() { int n, r; std::cin >> n; std::cin >> r; std::vector v(n); std::fill(v.begin(), v.begin() + r, true); do { for (int i = 0; i < n; ++i) { if (v[i]) { std::cout << (i + 1) << " "; } } std::cout << "\n"; } while (std::prev_permutation(v.begin(), v.end())); return 0; } 

    Un peu d'explication:

    Cela fonctionne en créant un "tableau de sélection" ( v ), où nous r sélecteurs r , puis nous créons toutes les permutations de ces sélecteurs, et imprimons le membre correspondant s'il est sélectionné dans la permutation actuelle de v . J'espère que cela t'aides.

    Vous pouvez l’implémenter si vous notez que pour chaque niveau, vous sélectionnez un nombre compris entre 1 et n .

    En C ++, nous devons garder «manuellement» l’état entre les appels qui produisent des résultats (une combinaison): nous construisons donc une classe qui initialise l’état lors de la construction et qui a un membre qui à chaque appel renvoie la combinaison : par exemple

     #include  #include  #include  #include  using namespace std; struct combinations { typedef vector combination_t; // initialize status combinations(int N, int R) : completed(N < 1 || R > N), generated(0), N(N), R(R) { for (int c = 1; c <= R; ++c) curr.push_back(c); } // true while there are more solutions bool completed; // count how many generated int generated; // get current and compute next combination combination_t next() { combination_t ret = curr; // find what to increment completed = true; for (int i = R - 1; i >= 0; --i) if (curr[i] < N - R + i + 1) { int j = curr[i] + 1; while (i <= R-1) curr[i++] = j++; completed = false; ++generated; break; } return ret; } private: int N, R; combination_t curr; }; int main(int argc, char **argv) { int N = argc >= 2 ? atoi(argv[1]) : 5; int R = argc >= 3 ? atoi(argv[2]) : 2; combinations cs(N, R); while (!cs.completed) { combinations::combination_t c = cs.next(); copy(c.begin(), c.end(), ostream_iterator(cout, ",")); cout << endl; } return cs.generated; } 

    sortie de test:

     1,2, 1,3, 1,4, 1,5, 2,3, 2,4, 2,5, 3,4, 3,5, 4,5, 
      #include using namespace std; for(int i=1;i<=5;i++) for (int j=2;j<=5;j++) if (i!=j) cout< 

    ma solution simple et efficace basée sur des algorithmes du Prof. Nathan Wodarz :

     // n choose r combination #include  #include  #include  struct c_unique { int current; c_unique() {current=0;} int operator()() {return ++current;} } UniqueNumber; void myfunction (int i) { std::cout << i << ' '; } int main() { int n=5; int r=3; std::vector myints(r); std::vector::iterator first = myints.begin(), last = myints.end(); std::generate(first, last, UniqueNumber); std::for_each(first, last, myfunction); std::cout << std::endl; while((*first) != n-r+1){ std::vector::iterator mt = last; while (*(--mt) == n-(last-mt)+1); (*mt)++; while (++mt != last) *mt = *(mt-1)+1; std::for_each(first, last, myfunction); std::cout << std::endl; } } 

    alors la sortie est:
    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

    Je suggérerais de trouver comment vous le feriez sur papier et en déduire le pseudocode. Après cela, il vous suffit de décider de la manière d’encoder et de stocker les données manipulées.

    Pour ex:

     For each result item in result array // 0, 1, ... r For each item possible // 0, 1, 2, ... n if current item does not exist in the result array place item in result array exit the inner for end if end for end for 

    Vous pouvez utiliser la récursivité pour choisir N ​​+ 1 combinaisons dans lesquelles vous choisissez N combinaisons, puis en append 1. Le 1 que vous ajoutez doit toujours être après le dernier de vos N, donc si votre N inclut le dernier élément, aucune combinaison N + 1 ne lui est associée.

    Peut-être pas la solution la plus efficace, mais cela devrait fonctionner.

    Le cas de base choisirait 0 ou 1. Vous pourriez choisir 0 et obtenir un ensemble vide. A partir d’un ensemble vide, vous pouvez supposer que les iterators travaillent entre les éléments et non pas sur eux.

    Le code est similaire à la génération de chiffres binarys. Conservez une structure de données supplémentaire, un tableau perm [], dont la valeur à l’index indiquera si un élément du tableau est inclus ou non. Et aussi garder une variable de compte. Chaque fois que compte == longueur de la combinaison, imprimez les éléments sur la base de perm [].

     #include // a[] : given array of chars // perm[] : perm[i] is 1 if a[i] is considered, else 0 // index : subscript of perm which is to be 0ed and 1ed // n : length of the given input array // k : length of the permuted ssortingng void combinate(char a[], int perm[],int index, int n, int k) { static int count = 0; if( count == k ) { for(int i=0; i= (k-count) ){ perm[index]=1; count++; combinate(a,perm,index+1,n,k); perm[index]=0; count--; combinate(a,perm,index+1,n,k); } } int main() { char a[] ={'a','b','c','d'}; int perm[4] = {0}; combinate(a,perm,0,4,3); return 0; } 

    c’est une méthode récursive que vous pouvez utiliser sur n’importe quel type. Vous pouvez effectuer une itération sur une instance de la classe Combinations (par exemple, le vecteur get () avec toutes les combinaisons, chaque combinaison est un vecteur d’objects. Ceci est écrit en C ++ 11.

     //combinations.hpp #include  template class Combinations { // Combinations(std::vector s, int m) iterate all Combinations without repetition // from set s of size ms = {0,1,2,3,4,5} all permuations are: {0, 1, 2}, {0, 1,3}, // {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5}, // {0, 4, 5}, {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} public: Combinations(std::vector s, int m) : M(m), set(s), partial(std::vector(M)) { N = s.size(); // unsigned long can't be casted to int in initialization out = std::vector>(comb(N,M), std::vector(M)); // allocate space generate(0, N-1, M-1); }; typedef typename std::vector>::const_iterator const_iterator; typedef typename std::vector>::iterator iterator; iterator begin() { return out.begin(); } iterator end() { return out.end(); } std::vector> get() { return out; } private: void generate(int i, int j, int m); unsigned long long comb(unsigned long long n, unsigned long long k); // C(n, k) = n! / (nk)! int N; int M; std::vector set; std::vector partial; std::vector> out; int count (0); }; template void Combinations::generate(int i, int j, int m) { // combination of size m (number of slots) out of set[i..j] if (m > 0) { for (int z=i; z(partial); // add to output vector } } } template unsigned long long Combinations::comb(unsigned long long n, unsigned long long k) { // this is from Knuth vol 3 if (k > n) { return 0; } unsigned long long r = 1; for (unsigned long long d = 1; d <= k; ++d) { r *= n--; r /= d; } return r; } 

    Fichier de test:

     // test.cpp // comstack with: gcc -O3 -Wall -std=c++11 -lstdc++ -o test test.cpp #include  #include "combinations.hpp" struct Bla{ float x, y, z; }; int main() { std::vector s{0,1,2,3,4,5}; std::vector ss{{1, .4, 5.0},{2, .7, 5.0},{3, .1, 2.0},{4, .66, 99.0}}; Combinations c(s,3); // iterate over all combinations for (auto x : c) { for (auto ii : x) std::cout << ii << ", "; std::cout << "\n"; } // or get a vector back std::vector> z = c.get(); std::cout << "\n\n"; Combinations cc(ss, 2); // combinations of arbitrary objects for (auto x : cc) { for (auto b : x) std::cout << "(" << bx << ", " << by << ", " << bz << "), "; std::cout << "\n"; } } 

    la sortie est:

    0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 5, 0, 2, 3, 0, 2, 4, 0, 2, 5, 0, 3, 4, 0, 3, 5, 0, 4, 5, 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,

    (1, 0,4, 5), (2, 0,7, 5), (1, 0,4, 5), (3, 0,1, 2), (1, 0,4, 5), (4, 0,66, 99), (2 , 0,7, 5), (3, 0,1, 2), (2, 0,7, 5), (4, 0,66, 99), (3, 0,1, 2), (4, 0,66, 99),

     void print(int *a, int* s, int ls) { for(int i = 0; i < ls; i++) { cout << a[s[i]] << " "; } cout << endl; } void PrintCombinations(int *a, int l, int k, int *s, int ls, int sp) { if(k == 0) { print(a,s,ls); return; } for(int i = sp; i < l; i++) { s[k-1] = i; PrintCombinations(a,l,k-1,s,ls,i+1); s[k-1] = -1; } } int main() { int e[] = {1,2,3,4,5,6,7,8,9}; int s[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; PrintCombinations(e,9,6,s,6,0); } 

    Pour le cas particulier de (n choisir r) , où r est une constante fixe, on peut écrire r boucles nestedes pour arriver à la situation. Parfois, lorsque r n’est pas fixé, nous pouvons avoir un autre cas particulier (n choisir nr) , où r est encore une constante fixe. L’idée est que chaque combinaison de ce type est l’inverse des combinaisons de (n choisir r). Nous pouvons donc à nouveau utiliser les boucles nestedes, mais inverser la solution:

     // example 1: choose each 2 from given vector and apply 'doSomething' void doOnCombinationsOfTwo(const std::vector vector) { for (int i1 = 0; i1 < vector.size() - 1; i1++) { for (int i2 = i1 + 1; i2 < vector.size(); i2++) { doSomething( { vector[i1], vector[i2] }); } } } // example 2: choose each n-2 from given vector and apply 'doSomethingElse' void doOnCombinationsOfNMinusTwo(const std::vector vector) { std::vector combination(vector.size() - 2); // let's reuse our combination vector for (int i1 = 0; i1 < vector.size() - 1; i1++) { for (int i2 = i1 + 1; i2 < vector.size(); i2++) { auto combinationEntry = combination.begin(); // use iterator to fill combination for (int i = 0; i < vector.size(); i++) { if (i != i1 && i != i2) { *combinationEntry++ = i; } } doSomethingElse(combinationVector); } } } 

    Vous pouvez simplement utiliser pour les boucles si r est petit, ici r = 2, donc deux pour les boucles:

     unsigned int i, j, max=0; for(i=1; i<=n; i++){ for(j=i+1; j<=n; j++){ int ans = (i & j); cout << i << " " << j << endl; } } 
     public static class CombinationGenerator { int n; int k; Integer[] input; List> output; public CombinationGenerator(int n, int k) { this.n = n; this.k = k; input = new Integer[n]; for (int i = 1; i <= n; i++) { input[i-1] = i; } } public List> generate(){ if(k>n){ throw new RuntimeErrorException(null, "K should be less than N"); } output = generate(0, k); printOutput(); return output; } private List> generate(int cur, int k) { List> output = new ArrayList>(); int length = input.length - cur; if(length == k){ List result = new ArrayList(); for (int i = cur; i < input.length; i++) { result.add(input[i]); } output.add(result); } else if( k == 1){ for (int i = cur; i < input.length; i++) { List result = new ArrayList(); result.add(input[i]); output.add(result); } } else{ for (int i = cur; i < input.length; i++) { List> partialResult = generate(i+1, k-1); for (Iterator> iterator = partialResult.iterator(); iterator .hasNext();) { List list = (List) iterator.next(); list.add(input[i]); } output.addAll(partialResult); } } return output; } private void printOutput(){ for (Iterator> iterator = output.iterator(); iterator .hasNext();) { printList((List) iterator.next()); } } private void printList(List next) { for (Iterator iterator = next.iterator(); iterator.hasNext();) { Integer integer = (Integer) iterator.next(); System.out.print(integer.intValue()); } System.out.print("\n"); } }