Permutation und Kombination in C ++ finden
Ich möchte eine Reihe von Zahlen dynamischer Länge in C ++ finden. Angenommen, ich habe 2 Gruppen von Zahlen: arr1[3] = {1, 3, 8}
und arr2[4] = {2, 9}
dann ist die erwartete Ausgabe:
'1, 2',
'1, 9',
'3, 2',
'3, 9',
'8, 2',
'8, 9'.
Wenn es jetzt jedoch 3 Gruppen gibt : arr1[3] = {1, 3, 8}
, arr2[2] = {2, 9}
und arr3[5] = {1, 3, 9}
dann sollte die Ausgabe sein:
'1, 2, 1',
'1, 2, 3',
'1, 2, 9',
'1, 9, 1',
'1, 9, 3',
'1, 9, 9',
'3, 2, 1',
'3, 2, 3',
'3, 2, 9',
'3, 9, 1',
'3, 9, 3',
'3, 9, 9',
und so weiter...
Es gibt also 3 x 2 x 3 = 18 Ergebnisse. Ich habe das Ergebnis für 2 Gruppen und 3 Gruppen mit der entsprechenden Anzahl von for-Schleifen erhalten.
Siehe diesen Code für 2 Gruppen:
for(int i=1;i<=5;i++) {
for (int j=1;j<=5;j++) {
cout << i << "," << j << "," << endl;
}
}
Aber dann muss ich unterschiedliche Codes für unterschiedliche Werte der Gruppennummer verwenden und die switch-Anweisung oder die if-else-Anweisung verwenden, um diesen Teil des Codes auszuwählen.
Dies wird eine große Hilfe sein. Danke im Voraus!
Ich habe Vektor anstelle von Arrays verwendet, da diese viel einfacher zu handhaben sind.
Der Trick besteht darin, die Positionen in den Arrays in lexikografischer Reihenfolge aufzulisten und dann die Werte an diesen Positionen anzuzeigen:
#include <vector>
#include <iostream>
using std::vector;
void permutate(vector<vector<int>> values)
{
// the positions in each vector
vector<size_t> pos(values.size());
do
{
// display one of each array at current position
for(size_t i = 0; i < values.size(); ++i)
{
std::cout << values[i][pos[i]] << ", ";
}
std::cout << std::endl;
// increment the last array's display position
size_t p = 0;
pos[p]++;
// while we get to the end of current array, return to 0 and carry to next position
while(pos[p] == values[p].size())
{
pos[p] = 0;
p++;
pos[p]++;
// return when the last array's position get to its size
if (p == values.size())
{
return;
}
}
}
while(true);
}
int main()
{
vector<int> arr1 = {1, 3, 8};
vector<int> arr2 = {2, 9};
vector<int> arr3 = {1, 3, 9};
vector<vector<int>> allThree = {arr1, arr2, arr3};
permutate(allThree);
}
Als nächstes wäre es eine gute Übung, sie so zu gestalten, dass Sie sie akzeptieren std::vector<std::vector<T>>