Geek Answers Handbook

Adding all permutations of vector elements

I have a harsh number of vectors:

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);

Now I want to add these vectors A1, ..., A5 so that I spawn all permutations and add them together:

(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)

I tried adding them together using 5 for loops, but this approach does not work when I have vectors A1, ... AN, since I cannot hardcode N for loops in code where "N" is user defined

+4
source share
5 answers

Something like this with recursive calls:

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;
}
+2
source

Can vectors be used? Then try using nested loops to add them together based on the vector size of the vectors instead of the for loop for each vector.

EDIT: :

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

, :

Input:

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

: =

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, , -.

+1

vector<vector<double>> A A1, A2... An.

, ,
vector<size_t> index.
0, A (.. 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]++;
    }
}

/ . ,
-...

+1

Perhaps I missed something, but it would not be so simple as concatenating all vectors into one vector:

std::vector<double> A_all;
A_all.insert(std::end(A_all), std::begin(A1), std::end(A1));
...
std::sort(std::begin(A_all), std::end(A_all));
if (A_all.size() >= 12)
{
    std::cout << "Are you sure?" << std::endl;
    std::exit(0);
}
std::vector<double> result;
do
{
    double sum = std::accumulate(std::begin(A_all), std::end(A_all), 0.0);
    result.push_back(sum); // should be almost the same for each entry
} while (std::next_permutation(std::begin(A_all), std::end(A_all));

Links: accumulate , next_permutation , number of permutations

Note. I have not compiled or tested this code.

+1
source

Here is a simple recursive version:

#include <vector>
#include <iostream>

using namespace std;

void gps(const vector< vector<double> >& data, size_t i=0, double s=0) {
    if (i == data.size()) // the index is past all vectors, (1)
        cout << s << endl;
    else
        // for each element of the current vector
        for (auto v : data[i])
            gps(data, i + 1, s + v);  // add the element to the sum
            // and do recursion for the next vector till we get to (1)
}

int main() {
    vector< vector<double> > data = { {4.0, 9.5, 6.8},
        {3.2, 2.1, 7.8, 9.0}, {5.8, 9.1}, {5.4}, {5.6, 7.2}};
    gps(data);
    return 0;
}

And the version without recursion:

#include <vector>
#include <iostream>

using namespace std;

void gps2(const vector< vector<double> >& data) {
    // calculate all possible permutations (multiply each vector length)
    size_t perms = 1;
    for (auto v : data)
        perms *= v.size();

    for (int i = 0; i < perms; ++i) {
        double s = 0; // initialize sum = 0
        size_t tmp = i;

        for (int j = data.size() - 1; j >= 0; --j) {
            size_t k = tmp % data[j].size(); // The reminder is the index
            tmp /= data[j].size(); // prepare for the next vector
            s += data[j][k]; // update the sum
        }
        cout << s << endl; // print the sum
    }
}

int main() {
    vector< vector<double> > data = { {4.0, 9.5, 6.8},
        {3.2, 2.1, 7.8, 9.0}, {5.8, 9.1}, {5.4}, {5.6, 7.2}};
    gps2(data);
    return 0;
}
0
source

More articles:


All Articles