come evitare questo errore for-loop in C++?

Question

Devo programmare tutti i set di numeri possibili da 1 a N per un numero arbitrario di numeri interi senza permutazione.

Dal momento che non so come spiegarlo meglio ecco alcuni esempi:

per m = 2

vector<vector<int>> box;  
int N = 5; 

for(int i = 1; i <= N; i++) { 
    for(int j = N; j >= i; j--) { 
     vector<int> dummy; 
     dummy.push_back(i); 
     dummy.push_back(j); 
     box.push_back(dummy); 
    } 
} 

per m = 3

vector<vector<int>> box;  
int N = 5; 

for(int i = 1; i <= N; i++) { 
    for(int j = N; j >= i; j--) { 
     for(int k = N; k >= j; k--) { 
      vector<int> dummy; 
      dummy.push_back(i); 
      dummy.push_back(j); 
      dummy.push_back(k); 
      box.push_back(dummy); 
     } 
    } 
} 

Questo funziona perfettamente bene e il risultato è ciò che di cui ho bisogno. Ma come già accennato, m può essere arbitrario e non posso essere preso la briga di implementarlo per m = 37 o altro. N e m sono valori noti ma cambiano mentre il programma è in esecuzione. Ci deve essere un modo migliore per implementare questo rispetto al caso m = 37 per implementare una riga di 37-per-loop. Qualcuno può aiutarmi? Sono un po 'incapace: \

modifica: per spiegare meglio quello che sto cercando qui sono alcuni altri esempi.

Diciamo N = 5 e m = 4, di 1223 è una soluzione fattibile per me, 124 non è dal momento che è a corto. Diciamo che ho già trovato 1223 come soluzione, che non ho bisogno di 2123, 2213 o di qualsiasi altra permutazione di questo numero.

edit2: O se preferisci una formulazione più visiva (matematica?) Del problema, qui vai.

Considerare m la dimensione. Con m stato 2 si rimane con una matrice di dimensioni N. Sto cercando il triangolo superiore (o inferiore) di questa matrice inclusa la diagonale. Passiamo a m = 3, la Matrix diventa un cubo tridimensionale (o Tensore se lo si desidera), ora sto cercando il tetraedro superiore (o inferiore) compresa la diagonale-piana. Per dimensioni superiori a 3, sto cercando l'iper tetraedro dell'ipercole, compreso il piano iper-diagonale.

Answer 1

http://howardhinnant.github.io/combinations.html

i seguenti algoritmi generici consentono un client di visitare ogni combinazione o permuation di una sequenza di lunghezza N, articoli R al momento.

Esempio utilizzo:

std::vector<std::vector<int>> box; 

std::vector<int> v(N); 
std::iota(begin(v), end(v), 1); 

for_each_combination(begin(v), begin(v) + M, end(v), [](auto b, auto e) { 
    box.emplace_back(b, e); 
    return false; 
}); 

Il codice di cui sopra dimostra l'inserimento di ogni combinazione in box come esempio, ma probabilmente non si vuole fare in realtà che: assumendo che box è semplicemente un intermediario e che il tuo lavoro effettivo poi lo usa da qualche altra parte, puoi evitare un intermediario e semplicemente fare tutto il lavoro che ti serve direttamente nel corpo del funtore.

Ecco uno complete, working example utilizzando il codice dal collegamento fornito.

---

Dal momento che ciò che si vuole è combinazioni con ripetizione piuttosto che solo combinazioni. Ecco un esempio di applicazione del presente sulla parte superiore del for_each_combination():

template<typename Func> 
void for_each_combination_with_repetition(int categories, int slots, Func func) { 
    std::vector<int> v(slots + categories - 1); 
    std::iota(begin(v), end(v), 1); 

    std::vector<int> indices; 
    for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) { 
     indices.clear(); 
     int last = 0; 
     int current_element = 0; 

     for(;b != e; ++last) { 
      if (*b == last+1) { 
       indices.push_back(current_element); 
       ++b; 
      } else { 
       ++current_element; 
      } 
     } 
     func(begin(indices), end(indices)); 
     return false; 
    }); 
} 

Wikipedia article on combinations mostra un buon esempio di ciò che questo sta facendo: si sta facendo tutte le combinazioni (senza ripetizione) dei numeri [0, N + M - 1) e poi cercando le "lacune" nei risultati. Gli spazi rappresentano transizioni da ripetizioni di un elemento a ripetizioni del successivo.

Il funtore che si passa a questo algoritmo ha un intervallo che contiene gli indici in una raccolta contenente gli elementi che si stanno combinando. Ad esempio, se vuoi ottenere tutti i set di tre elementi dall'insieme di {x, y}, i risultati desiderati sono {{x, x, x}, {x, x, y}, {x, y, y}, {y, y, y}}, e questo algoritmo rappresenta questo restituendo intervalli di indici nell'insieme (ordinato) {x, y}: {{0,0,0}, {0,0,1} , {0,1,1}, {1,1,1}}.

Quindi normalmente per utilizzare questo si dispone di un vettore o qualcosa che contiene i tuoi elementi e utilizzare gli intervalli prodotti da questo algoritmo come indici in quel contenitore. Tuttavia nel tuo caso, dal momento che gli elementi sono solo i numeri da 1 a N è possibile utilizzare gli indici direttamente con l'aggiunta di uno a ogni indice:

for_each_combination_with_repetition(N, M, [&](auto b, auto e) { 
    for(; b != e; ++b) { 
     int index = *b; 
     std::cout << index + 1 << " "; 
    } 
    std::cout << '\n'; 
}); 

Complete example

---

Un'implementazione alternativa può tornare vettori che rappresentano i conteggi di ciascuna categoria. Per esempio. i risultati precedenti {{x, x, x}, {x, x, y}, {x, y, y}, {y, y, y}} potrebbero essere rappresentati da: {{3,0} {2, 1}, {1,2}, {0,3}}. Modificare l'applicazione per la produzione di questa rappresentazione, invece si presenta così:

template<typename Func> 
void for_each_combination_with_repetition(int categories, int slots, Func func) { 
    std::vector<int> v(slots + categories - 1); 
    std::iota(begin(v), end(v), 1); 

    std::vector<int> repetitions(categories); 
    for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) { 
     std::fill(begin(repetitions), end(repetitions), 0); 

     int last = 0; 
     int current_element = 0; 

     for(;b != e; ++last) { 
      if (*b == last+1) { 
       ++repetitions[current_element]; 
       ++b; 
      } else { 
       ++current_element; 
      } 
     } 
     func(begin(repetitions), end(repetitions)); 
     return false; 
    }); 
} 

Answer 2

È possibile utilizzare la ricorsione per trovare tutti i sottoinsiemi. Questo può probabilmente essere migliorato stilisticamente, ma ecco un breve prendere il problema:

std::vector<std::set<int>> subsets(std::vector<int> x) 
{ 
    if (x.size() == 0) 
     return { std::set<int>() }; 
    else 
    { 
     int last = x.back(); 
     x.pop_back(); 

     auto sets = subsets(x); 
     size_t n = sets.size(); 

     for (size_t i = 0; i < n; i++) 
     { 
      std::set<int> s = sets[i]; 
      s.insert(last); 
      sets.push_back(std::move(s)); 
     } 

     return sets; 
    } 
} 

Questo raddoppia il numero di risposte ad ogni passo ricorsione: il numero di sottoinsiemi è 2^n, come previsto.

Se lo si desidera, è possibile sostituire std::set per std::vector.