Generazione di combinazioni in c ++

Ho cercato un codice sorgente per generare combinazioni usando c ++. Ho trovato alcuni codici avanzati per questo, ma questo va bene solo per i dati predefiniti di numeri specifici. Qualcuno può darmi qualche suggerimento, o forse qualche idea per generare una combinazione. Ad esempio, supponiamo che l’insieme S = {1, 2, 3, …., n} e ne preleviamo r = 2. L’input sarebbe n e r . In questo caso, il programma genererà array di lunghezza due, come 5 2 uscite 1 2, 1 3, ecc. Ho avuto difficoltà nella costruzione dell’algoritmo. Mi ci è voluto un mese a pensarci.

Un modo semplice usando 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; } 

o una leggera variazione che produce i risultati in un ordine più facile da seguire:

 #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 po 'di spiegazione:

Funziona creando un "array di selezione" ( v ), dove posizioniamo i selettori r , quindi creiamo tutte le permutazioni di questi selettori e stampiamo il membro del set corrispondente se è selezionato nella permutazione corrente di v . Spero che questo ti aiuti.

Puoi implementarlo se noti che per ogni livello r selezioni un numero compreso tra 1 e n .

In C ++, dobbiamo “manualmente” mantenere lo stato tra le chiamate che producono risultati (una combinazione): così, costruiamo una class che in fase di inizializzazione costruisce lo stato, e ha un membro che su ogni chiamata restituisce la combinazione mentre ci sono soluzioni : per esempio

 #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; } 

uscita di prova:

 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< 

la mia soluzione semplice ed efficiente basata su algoritmi del 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; } } 

quindi l'output è:
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

Ti suggerirei di capire come lo faresti su carta tu stesso e ne deduci uno pseudocodice. Dopodiché, devi solo decidere il modo di codificare e archiviare i dati manipolati.

Per esempio:

 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 

Puoi usare la ricorsione per scegliere N + 1 combinazioni, quindi scegli N combinazioni e aggiungi 1 ad essa. Il 1 che aggiungi deve sempre essere dopo l’ultimo di N, quindi se N include l’ultimo elemento non ci sono N + 1 associate ad esso.

Forse non è la soluzione più efficiente, ma dovrebbe funzionare.

Il caso base selezionerebbe 0 o 1. Puoi scegliere 0 e ottenere un set vuoto. Da un set vuoto si può ipotizzare che gli iteratori funzionino tra gli elementi e non su di essi.

Il codice è simile alla generazione di cifre binarie. Mantieni una struttura dati extra, una perm matrice [], il cui valore all’indice i dirà se l’elemento dell’array è incluso o meno. E mantieni una variabile di conteggio. Quando conti == lunghezza della combinazione, stampa gli elementi in base alla 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 string 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; } 

questo è un metodo ricorsivo, che puoi usare su qualsiasi tipo. puoi scorrere su un’istanza della class Combinations (es. o get () vettoriale con tutte le combinazioni, ogni combinazione è un vettore di oggetti, scritto in 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; } 

File di prova:

 // test.cpp // compile 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"; } } 

l'output è:

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); } 

Per il caso speciale di (n scegliere r) , dove r è una costante fissa, possiamo scrivere cicli ripetuti per arrivare alla situazione. A volte quando r non è fisso, potremmo avere un altro caso speciale (n scegliere nr) , dove r è di nuovo una costante fissa. L’idea è che ogni tale combinazione è l’inverso delle combinazioni di (n scegli r). Quindi possiamo nuovamente utilizzare loop n annidati, ma invertire la soluzione:

 // 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); } } } 

Puoi usare solo per cicli se r è piccolo, qui r = 2, quindi due per cicli:

 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"); } }