# Find all consecutive sequences in an ordered set

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

• Do you just want to print them out, or do you want them stored in all. – Dukeling Nov 13 '13 at 12:17
• @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! – Hani Gotc Nov 13 '13 at 12:19

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

• The static counters are kinda nasty, though. – 200_success Nov 14 '13 at 1:08

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

• 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]]

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.