添加向量元素的所有排列

Question

我有一个任意数量的向量：

vector<double> A1= (4.0, 9.5, 6.8)
vector<double> A2= (3.2, 2.1, 7.8,9.0)
vector<double> A3= (5.8, 9.1)
vector<double> A4= (5.4)
vector<double> A5= (5.6, 7.2);

现在我想将这些向量A1，..，A5相加，这样我就可以生成所有的排列并将它们相加：

(4.0 + 3.2 + 5.8 + 5.4 + 5.6)
(4.0 + 3.2 + 5.8 + 5.4 + 7.2)
(4.0 + 3.2 + 9.1 + 5.4 + 5.6)
(4.0 + 3.2 + 9.1 + 5.4 + 7.2)
(4.0 + 2.1 + 5.8 + 5.4 + 5.6)
(4.0 + 2.1 + 5.8 + 5.4 + 7.2)
(4.0 + 2.1 + 9.1 + 5.4 + 5.6)
(4.0 + 2.1 + 9.1 + 5.4 + 7.2)
(4.0 + 7.8 + 5.8 + 5.4 + 5.6)
(4.0 + 7.8 + 5.8 + 5.4 + 7.2)
(4.0 + 7.8 + 9.1 + 5.4 + 5.6)
(4.0 + 7.8 + 9.1 + 5.4 + 7.2)
(4.0 + 9.0 + 5.8 + 5.4 + 5.6)
(4.0 + 9.0 + 5.8 + 5.4 + 7.2)
(4.0 + 9.0 + 9.1 + 5.4 + 5.6)
(4.0 + 9.0 + 9.1 + 5.4 + 7.2)

(9.5 + 3.2 + 5.8 + 5.4 + 5.6)
(9.5 + 3.2 + 5.8 + 5.4 + 7.2)
(9.5 + 3.2 + 9.1 + 5.4 + 5.6)
(9.5 + 3.2 + 9.1 + 5.4 + 7.2)
(9.5 + 2.1 + 5.8 + 5.4 + 5.6)
(9.5 + 2.1 + 5.8 + 5.4 + 7.2)
(9.5 + 2.1 + 9.1 + 5.4 + 5.6)
(9.5 + 2.1 + 9.1 + 5.4 + 7.2)
(9.5 + 7.8 + 5.8 + 5.4 + 5.6)
(9.5 + 7.8 + 5.8 + 5.4 + 7.2)
(9.5 + 7.8 + 9.1 + 5.4 + 5.6)
(9.5 + 7.8 + 9.1 + 5.4 + 7.2)
(9.5 + 9.0 + 5.8 + 5.4 + 5.6)
(9.5 + 9.0 + 5.8 + 5.4 + 7.2)
(9.5 + 9.0 + 9.1 + 5.4 + 5.6)
(9.5 + 9.0 + 9.1 + 5.4 + 7.2)

(6.8 + 3.2 + 5.8 + 5.4 + 5.6)
(6.8 + 3.2 + 5.8 + 5.4 + 7.2)
(6.8 + 3.2 + 9.1 + 5.4 + 5.6)
(6.8 + 3.2 + 9.1 + 5.4 + 7.2)
(6.8 + 2.1 + 5.8 + 5.4 + 5.6)
(6.8 + 2.1 + 5.8 + 5.4 + 7.2)
(6.8 + 2.1 + 9.1 + 5.4 + 5.6)
(6.8 + 2.1 + 9.1 + 5.4 + 7.2)
(6.8 + 7.8 + 5.8 + 5.4 + 5.6)
(6.8 + 7.8 + 5.8 + 5.4 + 7.2)
(6.8 + 7.8 + 9.1 + 5.4 + 5.6)
(6.8 + 7.8 + 9.1 + 5.4 + 7.2)
(6.8 + 9.0 + 5.8 + 5.4 + 5.6)
(6.8 + 9.0 + 5.8 + 5.4 + 7.2)
(6.8 + 9.0 + 9.1 + 5.4 + 5.6)
(6.8 + 9.0 + 9.1 + 5.4 + 7.2)

我尝试使用5 for循环将它们加在一起，但是当我有A1，...AN向量时，这种方法不起作用，因为我不能在代码中硬编码N for循环，其中'N‘是用户定义的

Answer 1

首先，创建一个vector<vector<double>> A而不是A1，A2...An。

对于实际任务，非常简单但不是很快的解决方案，

首先，您需要一个vector<size_t> index。

用与A包含的向量一样多的0填充它(即，A.size())。

然后如下所示：

size_t i;
while(index[0] < A[0].size())
{
    //sum calculation
    double sum = 0.0;
    for(i = 0; i < A.size(); i++)
        sum += A[i][index[i]];
    cout << sum << endl; // or collect all sum´s in a vector, or...

    //index change / overflow detection
    i = A.size() - 1;
    index[i]++;
    while(index[i] >= A[i].size() && i > 0)
    {
        index[i] = 0;
        i--;
        index[i]++;
    }
}

不过，递归/堆栈解决方案会更快。

后者与上面的代码没有太大不同，

只是中间的和被存储在某个地方。

Answer 2

使用递归调用的代码如下所示：

void calculate(int sum, size_t n, vector<vector<int>>& va)
{
    if (va.size() > n)
    {
        for (auto x : va[n])
        {
            calculate(sum+x, n+1, va);
        }
    }
    else
    {
        cout << sum << endl;
    }
}

int main()
{
    vector<vector<int>> all;
    vector<int> A1 = {1, 2};
    vector<int> A2 = {5, 10};
    all.push_back(A1);
    all.push_back(A2);
    calculate(0, 0, all);
    return 0;
}

Answer 3

你能使用向量的向量吗？然后尝试使用嵌套循环，根据向量的向量大小将它们添加到一起，而不是每个向量的for循环。

编辑:如何实现：

vector double solutions; 
   for each inputVector
        oldSolution = solutions
        clear solutions
        for each element in an inputVector
            oldSolutionsCopy = oldSolution
            add the current element to every vector in solutions vector copy
            add oldSolutionsCopy to solutions

如果我认为这是正确的，那将会给出：

输入：

A = {0, 1, 2}
B = {b, c}
C = {y, z}

第一个循环给出: Solution=

sum({0})
sum({1})
sum({2})

第二个循环提供：

sum({0}{a})
sum({1}{a})
sum({2}{a})
sum({0}{b})
sum({1}{b})
sum({2}{b})

第三个循环提供：

sum({0}{a}{y})
sum({1}{a}{y})
sum({2}{a}{y})
sum({0}{b}{y})
sum({1}{b}{y})
sum({2}{b}{y})
sum({0}{a}{z})
sum({1}{a}{z})
sum({2}{a}{z})
sum({0}{b}{z})
sum({1}{b}{z})
sum({2}{b}{z})

它可能需要一些清理边缘情况，这只是一个丑陋的sudo代码，但我认为它工作哈哈。