1
\$\begingroup\$

I have the following set. a = [1,2,3,4,5] and i want to find all of the following sequences of consecutive elements:

1,
1,2
1,2,3
1,2,3,4
1,2,3,4,5
2,
2,3,
2,3,4,
2,3,4,5
3,
3,4
3,4,5
4
4,5
5

This is the following code that I use and works correctly. My only problem is with the complexity of the algorithm O(n2). Is there a better approach that I can use to reduce the complexity?

    int main()
    {
        int a[5] = {1,2,3,4,5};
           vector<vector<int>> all;
            for(int i = 0; i < 5; i ++)
            {
                vector<int> g;
                g.push_back(a[i]);
                all.push_back(g);
               for(int j = i+1; j < 5; j++)
               {
                    g.push_back(a[j]);
                    all.push_back(g);
               }
               g.clear();
            }

            for(int i = 0; i < all.size();i++)
            {
               for(int j = 0; j < all[i].size();j++)
               {
                    cout << all[i][j] << "  ";
               }
               cout << endl;
            }

        return 0;
    }
\$\endgroup\$
  • \$\begingroup\$ Do you just want to print them out, or do you want them stored in all. \$\endgroup\$ – Dukeling Nov 13 '13 at 12:17
  • \$\begingroup\$ @Dukeling I just want to store them in all. The printing part is just to test if my work was ok that's all. I can remove the printing part from the question, if it doesn't help. KEEP IN MIND: all is a vector of vectors. So every line in the output is a vector! \$\endgroup\$ – Hani Gotc Nov 13 '13 at 12:19
1
\$\begingroup\$

If only for comparison, counters first

static const int N( Max * (Max + 1) / 2); // number of all permutations
static int Max(5); // series upper bound
int vc(1); // vector counter
static int seed = 1; // counts upwards after each full series
static int vmax = seed; // starts at floor during every series

for each is passing every vector here

void v_perm(std::vector<int>& vref) {
    for (int i(0 + seed); i <= vmax; i++) { vref.push_back(i); }
    vmax++; // grows to ceiling
    if (Max < vmax) { seed++; vmax = seed; } // floor gets raised after each series
}

and main employs the for_each

int main() {
std::vector< std::vector<int> > all(N);
std::for_each(all.begin(), all.end(), v_perm);
}
\$\endgroup\$
  • \$\begingroup\$ The static counters are kinda nasty, though. \$\endgroup\$ – 200_success Nov 14 '13 at 1:08
2
\$\begingroup\$

As @MrSmith42 points out, the complexity can't be improved.

However, at the least, it would be a good habit to separate the routines for

  • initialization of your input
  • calculation
  • output

Here's how it could be better expressed in C++:

#include <iostream>
#include <vector>

using std::vector;

template<typename T>
std::ostream &operator<<(std::ostream &out, const vector<T> &v) {
    out << '[';
    for (typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i) {
        if (i != v.begin()) {
            out << ", ";
        }
        out << *i;
    }
    out << ']';
    return out;
}

template<typename T>
vector<vector<T> > consecutive_sequences(const vector<T> &v) {
    vector<vector<T> > all;
    for (typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i) {
        for (typename vector<T>::const_iterator j = i; j != v.end(); ++j) {
            all.push_back(vector<T>(i, j + 1));
        }
    }
    return all;
}

int main() {
    const int a[] = { 1, 2, 3, 4, 5 };
    const vector<int> a_vec(a, a + sizeof(a) / sizeof(a[0]));
    /* An alternative to the above in C++11…
     #include <numeric>
     vector<int> a_vec(5);
     std::iota(a_vec.begin(), a_vec.end(), 1);
    */

    std::cout << consecutive_sequences(a_vec) << std::endl;
    return 0;
}

Output:

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2], [2, 3], [2, 3, 4], [2, 3, 4, 5], [3], [3, 4], [3, 4, 5], [4], [4, 5], [5]]

\$\endgroup\$
2
\$\begingroup\$

You cannot get better than O(n²) because the result has the size of O(n²)

The Output has (n+1)*n/2 elements therefore you will always need O(n²) time to do the output.

You can only try to reduce the constant factor.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.