Wie bekomme ich alle möglichen Kombinationen von Vektor C++

Question

Ich habe ein Problem, und ich habe kämpfen um Stunden zu lösen, aber ich finde nicht den Weg.

Ich habe eine vector<vector<string>> mat die ich nicht kenne die Größe, das einzige, was ich weiß ist, dass es die gleiche Anzahl von Strings auf jedem Vektor gibt. Nun, was ich versuche zu tun, ist, alle möglichen Kombinationen dieser Strings wie zu bekommen: Stellen Sie sich vor, mat.size() = 3 und mat[0].size() = 3 (denken Sie daran, alle Vektoren haben die gleiche Anzahl von Zeichenfolgen, so dass es egal ist, wenn make mat[0].size() oder mat[3].size()), was Ich mag würde, ist alle Fäden zu bekommen auf diese

0,0 0,1 0,2 
0,0 0,1 1,2 
0,0 0,1 2,2 
0,0 1,1 0,2 
0,0 1,1 1,2 
0,0 1,1 2,2 
0,0 2,1 0,2 
0,0 2,1 1,2 
0,0 2,1 2,2 
1,0 0,1 0,2 

positioniert und so weiter ....

Jede Zeile auf einem neuen Array/Vektor

Jede Idee, gespeichert werden ?

EDIT (in Fall ist nicht wirklich klar):

Stellen Sie sich vor, dass mat die nächsten Daten hat:

mat[0] ={aa,bb,cc} 
mat[1] ={dd,ee,ff} 
mat[2] ={gg,hh,ll} 

was ich will irgendwie bekommen ist:

aa,bb,cc 
aa,bb,ff 
aa,bb,ll 
aa,ee,cc 
aa,ee,ff 
aa,ee,ll 
aa,hh,cc 
aa,hh,ff 
aa,hh,ll 

Und so on ...

Answer 1

Sie möchten grundsätzlich eine verschachtelte for-Schleife für jede Spalte Ihrer Matrix. Aber da die Anzahl der Spalten dynamisch ist, können Sie das nicht in der Zeile tun. Sie können eine rekursive Funktion mit einer for-Schleife verwenden, die über die Zeilen iteriert und die Spalte basierend auf einem Parameter auswählt, der bei jedem rekursiven Aufruf inkrementiert wird. Etwas wie folgt aus:

void permute_impl(size_t width, std::vector<std::vector<int>> const &mat, 
        size_t column, std::vector<int> &prefix) { 
    if (column < width) { 
    for (auto &row : mat) { 
     prefix.push_back(row[column]); 
     permute_impl(width, mat, column + 1, prefix); 
     prefix.pop_back(); 
    } 
    } else { 
    for (auto i : prefix) 
     std::cout << i << ' '; 
    std::cout << '\n'; 
    } 
} 

void permute(std::vector<std::vector<int>> const &mat) { 
    if (mat.empty()) 
    return; 
    std::vector<int> prefix; 
    size_t N = mat[0].size(); 
    // assert that all rows are the same size 
    for (auto &row : mat) 
    assert(row.size() == N); 
    permute_impl(N, mat, 0, prefix); 
} 

DEMO

Answer 2

vector<vector<string>> mat; // each interior vector has the same length 
// populate mat somehow... 

size_t width = mat.at(0).size(); 
vector<string> out(pow(mat.size(), width); 

// each value of first column is repeated (rows^(cols-1)) times 
size_t reps = out.size(); 
for (size_t col = 0; col < width; ++col) { 
    reps /= width; 
    for (size_t ii = 0; ii < out.size(); ++ii) { 
     if (ii != 0) { 
      out[ii].append(','); 
     } else { 
      out[ii].reserve(2 * width); // performance optimization 
     } 
     size_t row = ii/reps % mat.size(); 
     out[ii].append(mat[row][col]); // write one cell of output 
    } 
} 

Wenn wir im Voraus wusste, dass die Saiten etwas fester Länge hatten, konnten wir den reserve() Anruf optimieren, aber ich nehme nur jede Saite hat mindestens ein Zeichen .

Answer 3

Ich hatte keine Zeit, um dieses Problem zu lösen, aber ich habe für 10 Minuten versucht und ich denke, ich kann Ihre Frage beantworten. Ich denke, dass Sie alle möglichen Kombinationen finden wollen. Also meine Lösung in einer solchen paar Mal, dass ich das hätte, würde sein:

#include <iostream> 
#include <vector> 
#include <queue> 

using namespace std; 

// I define the vector<int> data type to be stored in the variable int_vector. 
typedef vector<int> int_vector; 

// The definition of the max index of the array. 
#define N 3 

// The Solve class. 
class Solve{ 
    public: 
     // The elements of an array! This is just for testing! 
     const int num[N] = {1, 2, 3}; 
     // The length of the array. That means the index of the last element. 
     const int length = N - 1; 
     // The vector that stores the possible combinations. 
     vector<int_vector> solution; 

     // The create_combination function. 
     void create_combinations(){ 

      // The queue to create the possible combinations. 
      queue<int_vector> combinations; 

      // A vector just to store the elements. 
      vector<int> test; 

      // I create the front vector of the queue. 
      for(int i = 0; i <= length; i++){ 
       // I push back to the vector the i-element of the num array. 
       test.push_back(num[i]); 
      } 

      // I push back to the queue the test vector. 
      combinations.push(test); 

      // This is just a variable to store some numbers laterin the loop. 
      int number; 
      // This loop runs forever EXCEPT if the condition that is refered in the if-statement later in te loop happens. 
      while(1){ 
       // This creates the possible combinations and push them back to the solution variable. 
       for(int sub_i = 0; sub_i <= length - 1; sub_i++){ 
        // I access the front element of the queue. 
        test = combinations.front(); 
        number = test[sub_i]; 
        test.erase(test.begin() + sub_i); 
        test.push_back(number); 
        combinations.push(test); 
        solution.push_back(test); 
       } 
       // The pop function erases the front element of the queue. That means that the next element of the queue becomes the front of the queue. 
       combinations.pop(); 
       //This is the condition that breaks the loop if it is true. 
       if(combinations.front()[2] == num[2]){ 
        break; 
       } 
      } 
     } 
}; 

// The main function. 
int main(){ 
    // I create the object of the Solve class. 
    Solve solve; 
    // I call the create_combinations function of the Solve class. 
    solve.create_combinations(); 
    // I access the solution variable of the Solve class and I store it to another variable called combinations. 
    vector<int_vector> combinations = solve.solution; 
    // This loop prints out to the screen the possible combinations 
    for(int i = 0; i <= 5; i++){ 
     for(int sub_i = 0; sub_i <= solve.length; sub_i++){ 
      cout << combinations[i].at(sub_i) << " "; 
     } 
     cout << endl; 
    } 

    return 0; 
} 

Wie man sehen kann ich es gelöst eine Warteschlange mit und ich speichern die Kombinationen in einem Vektor.