CODEWITHSUNDEEP
c++algorithm
Saurabh Sangpal
Saurabh Sangpal

Reputation: 101

Can I get rid of nested for loops here?

I have a function that takes a vector and returns a vector by combining all the elements in it. Right now, I have 3 nested for loops that create a combination that is 3 levels deep. I would like it to look better and have the ability to add the functionality to make it 4 levels deep when I want.

If input = ["one", "two", "three"]

3 level output = "onetwothree" "twoonethree" and so on.

std::vector<std::string> generator(std::vector<std::string>& x)
{
    std::vector<std::string> output;
    std::string tmp;
    for (auto i : x) {
        output.push_back(i);
        for (auto j : x) {
            tmp = i + j;
            output.push_back(tmp);
            for (auto k : x) {
                tmp = i + j + k;
                output.push_back(tmp);
            }
        }
    }
    return output;
}

I have looked into iterators, but I can't figure out if it would work.

Upvotes: 3

Views: 574

Answers (3)

wooohooo
wooohooo

Reputation: 636

Hi I had the similar problem in Python once.

The goal I suppose is to have a "n-nested" loops such that n is a variable. A better result would be to make each index I_i of level i be variables. That is to say, given a list [I_1,I_2,...,I_n], you should be able to generate such loop

for i_1 in range( I_1):
    for i_2 in range( I_2):
       ...
          for i_n in range(I_n):
             some_function(i_1,i_2,...,i_n)

One way to do this is to use mathematics. You can build a number such that on the ith digit, it's I_i based. This number's maxmium value is just I_1*I_2*...*I_n. In this way, the entire loop will be collaped into one simple loop

for i in range(I_1*I_2*...*I_n):
    # obtain these numbers
    i_1 = f_1(i)
    i_2 = f_2(i)
    ...
    i_n = f_n(i)
    some_function(i_1,i_2,...,i_n)

Although the functions to obtain the is are a bit complicated.

Another way to do it is, as you have mentioned, iterators. In Python it's just import itertools. In C++, however, I found this cppitertools. I haven't tried it, but I suppose this could work.

Still, if you want speed, the first approch is preferred. Still, I think there are better solutions.

Upvotes: 0

Georgi Gerganov
Georgi Gerganov

Reputation: 1066

If you want to generate all combinations of N words with max length L you could use this:

std::vector<std::string> generator(const std::vector<std::string> & x, int levels) {
    int nWords = x.size();

    std::vector<std::string> output;
    for (int l = 1; l <= levels; ++l) {
        int nCombs = std::pow(nWords, l); 
        for (int i = 0; i < nCombs; ++i) {
            std::string cur;
            for (int j = 0, k = i; j < l; ++j) {
                cur += x[k%nWords];
                k /= nWords;
            }
            output.push_back(cur);
        }
    }

    return output;
}

Live Example

There are still 3 nested loops, but this works for any value of L - not just 3. L > N also works.

Upvotes: 2

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

If what you are looking for is to simply generate the permutations of all the elements of the string vector x and store these permutations into another output vector, this is easily accomplished by using std::next_permutation and std::accumulate:

#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <algorithm>

std::vector<std::string> generator(std::vector<std::string> x)
{
    std::vector<std::string> output;
    std::sort(x.begin(), x.end());
    do 
    {
        output.push_back(std::accumulate(x.begin(), x.end(), std::string()));
    } while (std::next_permutation(x.begin(), x.end()));
    return output;
}

int main()
{
    auto v = generator({"one","two","three"});
    for (auto& val : v)
        std::cout << val << "\n";
}

Live Example

The std::accumulate basically calls operator + on the elements by default, thus the string is automatically concatenated.

As far as std::next_permutation, the description of what it does is explained at the link. Basically you want to start out with a sorted sequence, and call std::next_permutation to get the next permutation of elements.

Note that this is not contingent of the number of "levels" (as you call it). You could have a vector of 10 strings, and this would work correctly (assuming there are no memory constraints).

Upvotes: 8

Related Questions