C++中的笛卡尔积

Question

几周来我一直在寻找如何编写一段可以应用笛卡尔积的代码。假设我有两个数组：

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)。请帮助:(

Answer 1

下面是一个使用向量实现笛卡尔积的简单示例。矢量是更好的选择，因为我们不需要担心它的大小，因为它会动态改变它。

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

这里是 link 我实现上面代码的地方。虽然我不会 post 解决方案直接与您的问题相关，但评论中 posted 的链接已经包含答案，这就是为什么我 posted.

Answer 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 要好得多 - 它更快（在开发时间方面）并且可以避免许多错误。

Answer 3

#include <iostream>
#include <iterator>
#include <vector>
#include <utility>
#include <tuple>

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,a)(1,b)(1,c)(1,d)(1,e)(1,f)(2,a)(2,b)(2,c)(2,d)(2,e)(2,f)(3,a)(3,b)(3,c)(3,d)(3,e)(3,f)

您也可以将此功能应用到您的案例中：

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)

http://coliru.stacked-crooked.com/a/3ce388e10c61a3a4

Answer 4

这是一个实现，其中值的序列是一个参数（而不是像所有其他实现中的 pre-known）：

void CartesianRecurse(vector<vector<int>> &accum, vector<int> stack,
    vector<vector<int>> sequences, int index)
{
    vector<int> sequence = sequences[index];
    for (int i : sequence)
    {       
        stack.push_back(i);
        if (index == 0)
            accum.push_back(stack);
        else
            CartesianRecurse(accum, stack, sequences, index - 1);
        stack.pop_back();
    }
}
vector<vector<int>> CartesianProduct(vector<vector<int>> sequences)
{
    vector<vector<int>> accum;
    vector<int> stack;
    if (sequences.size() > 0)
        CartesianRecurse(accum, stack, sequences, sequences.size() - 1);
    return accum;
}

main() {
    vector<vector<int>> sequences = { {1,2,7},{3,4},{5,6} };
    vector<vector<int>> res = CartesianProduct(sequences);
    // now do something with the result in 'res'.
}

Answer 5

没有for循环的解决方案。

#include<array>
#include<iostream>
#include<tuple>
#include<utility>

template
<typename T, typename Tuple, std::size_t... I>
auto cartesian_product_base(
                         const T& a,
                         const Tuple& t,
                         std::index_sequence<I...>) {
    return std::make_tuple(std::make_pair(a, std::get<I>(t))...);
}

template
<typename T, typename... Ts, std::size_t... I>
std::array<T, sizeof...(Ts) + 1> to_array(std::tuple<T, Ts...> t, std::index_sequence<I...>) {
    return {std::get<I>(t)...};
}

template
<typename Tuple1, typename Tuple2, std::size_t... I>
auto cartesian_product_impl(
                         const Tuple1& t1,
                         const Tuple2& t2,
                         std::index_sequence<I...>) {
    return std::tuple_cat(cartesian_product_base(
                                 std::get<I>(t1),
                                 t2,
                                 std::make_index_sequence<std::tuple_size<Tuple2>::value>{})...);
}

template
<typename T1, std::size_t N1, typename T2, std::size_t N2>
auto cartesian_product(
                     const std::array<T1, N1>& a1,
                     const std::array<T2, N2>& a2) {
    return to_array(
                    cartesian_product_impl(a1, a2, std::make_index_sequence<N1>{}),
                    std::make_index_sequence<N1 * N2>{});
}

using namespace std;

int main() {
    array<int, 2> M = {1, 2};
    array<int, 3> J = {0, 1, 2};
    auto C = cartesian_product(M, J);
    cout << C.size() << endl;
    cout << "{";
    for (size_t i = 0; i != C.size(); ++i) {
        if (i != 0) {
            cout << ", ";
        }
        cout << "(" << C[i].first << ", " << C[i].second << ")";
    }
    cout << "}" << endl;
}

C++中的笛卡尔积

Cartesian Product in c++

c++

cartesian-product