Декартово произведение в переполнении стека
Я неделями искал, как придумать кусок кода, к которому я мог бы применить декартово произведение. Допустим, у меня есть два массива:
int M[2]= {1,2};
int J[3] = {0,1,2};
Таким образом, код будет принимать эти два массива в применении правила M X J
поэтому у нас будут пары (1,0) (1,1) (1,2) (2,0) (2,1) (2,2), и я хочу, чтобы новый результат был сохранен в новом массиве, где каждый индекс в массиве содержит пару, например, c [0] = (1,0).
Помогите, пожалуйста 🙁
Решение
Вот простой пример реализации декартового произведения с использованием вектора. Векторы — намного лучший выбор, так как нам не нужно беспокоиться о его размере, поскольку он динамически меняет его.
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int main() {
int M[2]= {1,2};
int J[3] = {0,1,2};
vector<pair<int,int>> C;
for (int i = 0; i < sizeof(M)/sizeof(M[0]); i++)
{
for (int j = 0; j < sizeof(J)/sizeof(J[1]); j++)
{
C.push_back(make_pair(M[i],J[j]));
}
}
/*
for (vector<int>::iterator it = C.begin(); it != C.end(); it++)
{
cout << *it << endl;
}
*/
for (int i = 0; i < C.size(); i++)
{
cout << C[i].first << "," << C[i].second << endl;
}
}
Здесь ссылка на сайт где я реализовал приведенный выше код. Хотя я бы не стал публиковать решение, непосредственно связанное с вашим вопросом, ссылки, размещенные в комментариях, уже содержат ответ, поэтому я и разместил.
Другие решения
#include <iostream>
#include <iterator>
#include <vector>
#include <utility>
template<typename Range1, typename Range2, typename OutputIterator>
void cartesian_product(Range1 const &r1, Range2 const &r2, OutputIterator out) {
using std::begin; using std::end;
for (auto i = begin(r1);i != end(r1); ++i) {
for (auto j = begin(r2); j != end(r2); ++j) {
*out++ = std::make_tuple(*i, *j);
}
}
}
int main() {
std::vector<int> a{1,2,3};
std::vector<char> b{'a','b','c','d','e','f'};
std::vector<std::tuple<int, char>> c;
cartesian_product(a, b, back_inserter(c));
for (auto &&v : c) {
std::cout << "(" << std::get<int>(v) << "," << std::get<char>(v) << ")";
}
}
Печать:
(1, а) (1, б) (1, с) (1, д) (1, е) (1, е) (2, а) (2, б) (2, с) (2, д) (2, е) (2, е) (3, а) (3, б) (3, с) (3, г) (3, е) (3, е)
И вы также можете применить функцию к вашему делу:
template<typename T, int N> constexpr int size(T (&)[N]) { return N; }
int main() {
int M[2] = {1,2};
int J[3] = {0,1,2};
std::tuple<int, int> product[size(M) * size(J)];
cartesian_product(M, J, product);
for (auto &&v : product) {
std::cout << "(" << std::get<0>(v) << "," << std::get<1>(v) << ")";
}
}
Выход:
(1,0) (1,1) (1,2) (2,0) (2,1) (2,2)
Я думаю, что использование двумерных массивов c ++ — очень плохая идея, но если вы хотите, вы, вероятно, могли бы использовать этот код
#include <iostream>
int** cartesian_prod( int* s1, int* s2, int s1size, int s2size )
{
int ressize = s1size*s2size;
int** res = new int*[ressize];
for ( int i = 0; i < s1size; i++ )
for ( int j = 0; j < s2size; j++ )
{
res[i*s2size+j] = new int[2];
res[i*s2size+j][0] = s1[i];
res[i*s2size+j][1] = s2[j];
}
return res;
}
int main() {
int M[2]= {1,2};
int J[3] = {0,1,2};
int** res;
int Msize = sizeof(M)/sizeof(M[0]);
int Jsize = sizeof(J)/sizeof(J[1]);
res = cartesian_prod(M, J, Msize, Jsize);
for ( int i = 0; i < Msize*Jsize; i++ )
std::cout << res[i][0] << " " << res[i][1] << std::endl;
for (int i = 0; i < Msize*Jsize; i++)
delete[] res[i];
delete[] res;
return 0;
}
Но гораздо лучше иметь дело с std :: vector — он намного быстрее (с точки зрения времени разработки) и избавит вас от многих ошибок.