如果我们 select 来自每个 Y 向量的一个值，则 X 数的每一种组合都是可能的

Question

如果这个问题有一个正式的名称（或者这是一个重复的问题，我还没有找到合适的问题来查看）然后指出我实际上应该搜索的内容也将不胜感激！但是，我还没有找到任何关于这个特定问题的讨论或方法。

我尽量让问题简单明了，如果有更多详细信息，请告诉我。

假设我们有四个随机长度的整数向量：

std::vector<int> v1 {1, 7, 5, 2};
std::vector<int> v2 {4, 2, 1};
std::vector<int> v3 {1, 9, 4, 6, 4, 1, 2};
std::vector<int> v4 {9, 4};

在这四个向量中，我需要生成所有可能的组合，其中我们一次只从每个源向量 (v1 - v4) select 生成一个整数。结果应该是我们从源向量中生成每个可能的 N 长度数字，其中 N = 源向量的数量（在本例中为 4）。

一些可能的组合很容易生成，例如 select 仅从每个源向量中提取第一个数字：

1 4 1 9

选择每个源向量的最后一个数字：

2 1 2 4

我遇到的问题是生成每一个可能的组合。我需要每个可能的 N 长度数字，这些数字可以通过组合来自 4 个源向量中的每一个的一个整数来创建。

谢谢！

Answer 1

这是一个包含任意数量输入向量的答案：

将索引配置视为一个数字，由不同数字系统中的数字组成。然后考虑计算一组索引，就像在某些数字系统中计算一个常规数字一样。例如，对于大小为 3 5 2 5 的四个向量，索引集 0 2 1 4 将导致 0 3 0 0。

对于以下代码，我假设您的向量是在另一个向量中给出的，即 vector<vector<int> >

这里有一个 class 用于索引：

class Indices {

private:
    vector<size_t> indices;
    vector<size_t> maximal_sizes;
    bool _max_reached;

public:

    Indices(const vector<vector<int> >& vectors) : indices(vectors.size(), 0), maximal_sizes(vectors.size()), _max_reached(false) {

        for(size_t i = 0; i < vectors.size(); i++){
            maximal_sizes[i] = vectors[i].size();
        }
    }

    const size_t& operator[] (const size_t i) const { return indices[i]; }
    bool max_reached() const { return max_reached; }

    void count_up() {

        size_t current = 0;
        while(current < indices.size()){
            indices[current]++;
            if(indices[current] >= maximal_sizes[current]){
                indices[current] = 0;
                current++;
            } else {
                return;
            }
        }
        _max_reached = true;
    }

}

（将其拆分为 header 和来源）

并像

一样使用它

inline void print(const vector<vector<int> >& vectors, const Indices& indices){

    for(size_t i = 0; i < vectors.size(); i++){
        cout << vectors[i][Indices[i]] << " ";
    }
    cout << endl;
}

void all_combinations(const vector<vector<int> >& vectors){

    Indices indices(vectors);

    while(not indices.max_reached()){
        print(vectors, indices);
        indices.count_up();
    }
}

（可能不完全是这样的功能，但你明白了。另外，我认为 Indices 的描述性不够，但现在想不出一个好的短名称。 max_reached 机械师有点烦我，看起来不优雅。如果有人有改进这个的想法，我很想听听。）

Answer 2

您确实在描述您的集合 Cartesian product。就像普通的数字乘积一样，这是对两个事物的运算，但它可以连续应用于两个以上的事物：

A x B x C x D = A x (B x (C x D))

该结构是理解问题的关键。您可以将其分解为递归子问题，每个子问题只涉及两个集合。这样你就可以处理任意数量的集合。

解题的程序也可以是递归的，也可以是迭代的。以下是使用 vector<int> 表示的集合的 lists 的半优化递归解决方案。给定一个集合列表

A, ...

它计算两个事物的笛卡尔积：A，以及其余集合的笛卡尔积：

A x (...)

您可以重新安排此过程以从基本情况开始向上，即 ((D x C) x B) x A。这样您就可以只使用循环而不是递归调用。但是思考问题的递归结构是很好的整理思路。

void cartesian_product( list< vector<int> > sets, list< vector<int> >& product) {
        if ( sets.empty() )
                return;

        // get first set
        auto& s = sets.front();

        // base case
        if ( ++begin( sets ) == end( sets ) ) {
                for ( auto k : s ) {
                        product.push_back( { k } );
                }
                return;
        }

        // get cartesian product of the rest of the sets
        cartesian_product( list< vector<int> >( ++begin( sets ), end( sets ) ), product );

        // make additional copies of product and append each element of first set to them
        list< vector<int> > additions;
        for ( auto k = ++begin( s ); k != end( s ); ++k ) {
                list< vector<int> > ad = product;
                for ( auto& x : ad ) {
                        x.push_back( *k );
                }
                additions.splice( end( additions ), ad );
        }

        // append the first element of the first set to the original product
        for ( auto& x : product ) {
                x.push_back( s.front() );
        }

        // append the additions to the final product
        product.splice( end( product ), additions );

        return;
}

这是程序的其余部分：

#include <cassert>
#include <iostream>
#include <list>
#include <vector>

using std::vector;
using std::list;
using std::cout;
using std::endl;

void cartesian_product( list< vector<int> > sets, list< vector<int> > &product);

int main( int argc, char *argv[] ) {
        list< vector<int> > sets = {
                {1, 7, 5, 2},
                {4, 2, 1},
                {1, 9, 4, 6, 4, 1, 2},
                {9, 4}
        };

        list< vector<int> > product;
        cartesian_product( sets, product );

        for ( auto& x : product ) {
                cout << "{ ";
                for ( auto k : x ) {
                        cout << k << " ";
                }
                cout << "}" << endl;
        }
}

如果我们 select 来自每个 Y 向量的一个值，则 X 数的每一种组合都是可能的

Every combination of X numbers possible if we select one value from each of Y vectors

c++

cartesian-product