Adding all permutations of vector elements

Question

I have an arbitary 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 in the manner such that I generate 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 to add them together using 5 for loops but this approach does not work when I have A1,...AN vectors as I can not hard code N for loops in code, where 'N' is user defined

...or a vector of vectors. About the 5 loops: Recursion or a self-build stack (again in a vector) with according logic, or a index array, or... — deviantfan, Apr 10 '15 at 13:51
saying that you have an *arbitrary* number of *variables* is silly. it's completely unrealistic. surely you're not into metaprogramming... — Karoly Horvath, Apr 10 '15 at 13:51
Of possible interest: http://stackoverflow.com/questions/2211915/combination-and-permutation-in-c — swalog, Apr 10 '15 at 13:54
@deW1 Seems like a nice idea can u please explain it a little more — Jannat Arora, Apr 10 '15 at 13:58
@MarcGlisse Oops sorry. I thought its a permutation. Thanks for correcting — Jannat Arora, Apr 10 '15 at 14:01

deviantfan · Answer 1 · 2015-04-10T14:05:23.137

First, make a vector<vector<double>> A instead of A1,A2...An.

For the actual task, very easy but not very fast solution,
first you need a vector<size_t> index.
Fill it with as many 0´s as A contains vectors (ie. A.size()).
Then something like this:

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]++;
    }
}

Recursive/stack solutions will be faster though.
Latter is not that different to the code above,
only that a indermediate sum is stored somewhere...

score 2 · Answer 2 · answered Apr 10 '15 at 14:06

Something like this using 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;
}

Bob · Answer 3 · 2015-04-10T15:29:31.687

1

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

EDIT: How it can be done:

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

If I thought that through correctly that would give:

Input:

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

First loop gives: Solution=

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

Second loop gives:

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

Third loop gives:

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

It might need some cleanup on edge cases, and this is just an ugly sudo code, but I think it works haha.

edited Apr 10 '15 at 15:29

answered Apr 10 '15 at 13:53

Bob

1,779
3
22
35

Nested loops won´t go well with eg. 1000 vectors, – deviantfan Apr 10 '15 at 14:00
@Ian - I think the problem is that you can't write it as nested for loops because you don't know how many for-loops you need to nest. If you knew the maximum number of input-vectors then it could be done but as deviantfan says it will be a pain for 1000 vectors. – Support Ukraine Apr 10 '15 at 14:22
@nielsen if you see my edit I believe that is a valid solution that can handle any number of vectors, though I agree with you execution time will get super gross as the size gets larger. – Bob Apr 10 '15 at 15:35
@Ian - Your text say "nested for-loops". I guess that gave the impression that you wanted to do `for(...) { for (...) { for (...) .......` which would be bad. And maybe the reason for the down votes (which btw didn't come from me). – Support Ukraine Apr 10 '15 at 15:43
Haha yeah I see what you mean, I could have explained myself better. Just after I got down voted I doubted my initial thought on the solution and had to go back and make sure it actually worked lol. – Bob Apr 10 '15 at 15:45

score 1 · Answer 4 · answered Apr 10 '15 at 17:37

Maybe I am missing something, but would it not be as easy as concatenating all the 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));

References: accumulate, next_permutation, number of permutations

Note: I did not compile and test this code.

Doncho Gunchev · Answer 5 · 2015-04-10T16:18:14.653

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

Adding all permutations of vector elements

5 Answers5