Algorithm loop combination

Question

I have 10 text files containing one column of 1,-1,0. I want to set a combination which sum the elements of each file.

For example, if I want to see all the combinations of 2 files among 10 files, I would create the 2 loops below: double sum;

for(int i;i=0;i<n;i++){
    for(int j;j=i;j<n;j++){
        sum += x[i]+x[j];
    }
}

Another example, if I want to see all the combinations of 3 files among 10 files, I would create the 3 loops below:

for(int i;i=0;i<n;i++){
    for(int j;j=i;j<n;j++){
        for(int k;k=j;k<n;k++)
           sum += x[i]+x[j]+x[k];
        }
    }
}

and so on, if I want to see the combinations x files among 10 files, I would create x loops.

My question is: I am looking for an algorithm which determines the number of loops by choosing x. If x=2, then I create 2 loops, if x=3, then I create 3 loops, if x=4, then I create 4 loops, ... or may be there is another way. Many thanks

And if you had 50 files, 50 nested loops?? That's insane. Needless to say, there are better ways, such as using `std::next_permutation` along with some logic to generate combinations (there are **many** examples here on SO) where you need one (or two) loops, regardless of the number of items. — PaulMcKenzie, Aug 14 '16 at 08:39
@PaulMcKenzie `std::next_permutation` looks not very useful here since the TS needs combinations, not permutations — alexeykuzmin0, Aug 14 '16 at 09:02
@alexeykuzmin0 -- You're mistaken. You can use a `std::next_permutation` to produce combinations if you put [some effort into it.](http://stackoverflow.com/questions/9430568/generating-combinations-in-c). The trick is to use a control array that consists of boolean values. — PaulMcKenzie, Aug 14 '16 at 09:05

score 1 · Answer 1 · answered Aug 14 '16 at 08:54

I'm not sure if the code you provided really works as for (int i;i=0;i<n;++i) most likely has to be for (int i=0;i<n;++i). Though that aside, you are searching for some kind of recursion.

Let me assume you have stored this data in an std::vector, than I would recommend creating a 2D variant std::vector<std::vector<int>>.

Having recursion requires 2 elements: the stop condition and the recursing:

void function(int &sum, const std::vector<std::vector<int>> &data, std::size_t outerLevel, std::size_t innerLevel, int intermediate) {
    // Stop condition of recursion,
    // if we don't have any elements any more,
    // the intermediate is our final result.
    if (outerLevel == data.size()) {
        sum += intermediate;
        return;
    }

    // Recursing
    const std::vector<int> &subData = data[outerLevel];
    for (auto i = innerLevel; i < subData.size(); ++i) {
        function(sum,
                 data,
                 outerLevel+1, // Go to the next std::vector<int>
                 i,            // Make sure the next inner loop starts at the right index
                 intermedite+subData[i] // Take the intermidiate sum
                 );
    }
}

// Wrapper to hide itermediate calculation variables
int functionWrapper(const std::vector<std::vector<int>> &data) {
    int sum = 0;
    function(sum, data, 0, 0, 0);
    return sum;
}

score 0 · Answer 2 · answered Aug 14 '16 at 13:06

0

If you just want to compute the sum, it is even simple as

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        sum += x[i] + x[j];
    }
}

is equivalent to

for (int i = 0; i < n; i++) {
    sum += (n - i) * x[i];
    for (int j = i; j < n; j++) {
        sum += x[j];
    }
}

and with some more effort

sum += (n + 1) * std::accumulate(std::begin(x), std::end(x), 0);

and for 3

const int sumx = std::accumulate(std::begin(x), std::end(x), 0);
sum += ((n + 1) * (n + 2) / 2) * sumx;

answered Aug 14 '16 at 13:06

Jarod42

203,559
14
181
302

I would like to thank you all of you who have answered so quickly to my question. I will study the answers and will come back with a code if I understand. I have to say I need to spend some time on it to make sure I understand the algorithm. First, I will study PaulMcKenzie – pchiknagi Aug 14 '16 at 15:14

Algorithm loop combination

2 Answers2