All integer sequences given amount of integers and length of sequence Given two integers, X and Y, you must create all possible integer sequences of length Y using the numbers from 1 to X.

For certain reasons, the function must return a deque&lt;deque&lt;int&gt; &gt; representing such (the primary deque holds all my sequences - each of then is a deque of ints).

This is not a permutation generator.

Example Input

X = 3, Y = 3


This means that I require sequences of length 3 each one. To compose the sequences, I use the integers 1, 2, and 3.

Example Output

The previous input should produce:

1 1 1 
1 1 2 
1 1 3 
1 2 1 
1 2 2 
1 2 3 
1 3 1 
1 3 2 
1 3 3 
2 1 1 
2 1 2 
2 1 3 
2 2 1 
2 2 2 
2 2 3 
2 3 1 
2 3 2 
2 3 3 
3 1 1 
3 1 2 
3 1 3 
3 2 1 
3 2 2 
3 2 3 
3 3 1 
3 3 2 
3 3 3 


My Idea

I'm not very good with this stuff. My approach is:


Create a start and end integer

Start is 1 repeated Y times. So in the previous example it is 111
End is X repeated Y times. So in the previous example it is 333

I count i from start to end.

If i contains an invalid digit (like 4, 5,...), abort this sequence.
If i is valid, then this sequence is valid, thus add it to my resulting deque.
When a sequence is valid, due to my needs, I split the integer and make a deque of each of its digits.



Why I need a review

I think it is pretty clear that this method doesn't sound very efficient. So many wasted iterations! Can you help me improve this code, and, perhaps, shorten it?

My Attempt

Note, you may notice that instead of "sequences" I call then "procedures".

#include &lt;iostream&gt;
#include &lt;sstream&gt;
#include &lt;deque&gt;

using namespace std;

// Converts a value to any type
template &lt;typename T,typename S&gt;
T convert(S original) {
    stringstream ss; ss &lt;&lt; original;
    T result; ss &gt;&gt; result;
    return result;
}

// The actual function
deque&lt;deque&lt;int&gt; &gt; allPossibleProcedures(int values, int depth) {
    deque&lt;deque&lt;int&gt; &gt; result;
    // I create a start point and an end point for my counting
    string minString; for (int d = 0; d &lt; depth; ++d) { minString.append("1"); }
    string limitString; for (int d = 0; d &lt; depth; ++d) { limitString.append(convert&lt;string&gt;(values)); }
    int start = convert&lt;int&gt;(minString);
    int limit = convert&lt;int&gt;(limitString);
    // I begin counting
    for (int i = start; i &lt;= limit; ++i) {
        deque&lt;int&gt; procedure;
        string text = convert&lt;string&gt;(i);
        bool ok = true;
        for (int c = 0; c &lt; text.length() &amp;&amp; ok; ++c) {
            int x = convert&lt;int&gt;(text.at(c));
            if (x &lt;= values &amp;&amp; x &gt; 0) {
                // This is a valid character. Add to procedure.
                procedure.push_back(x);
            }else{
                // Not a valid character. Abort this procedure.
                ok = false;
                break;
            }
        }
        if (ok) {
            result.push_back(procedure);
        }
    }
    return result;
}

int main(int argc, const char * argv[]) {
    deque&lt;deque&lt;int&gt; &gt;procedures = allPossibleProcedures(3,3);
    for (int i = 0; i &lt; procedures.size(); ++i) {
        for (int j = 0; j &lt; procedures[i].size(); ++j) {
            cout &lt;&lt; procedures[i][j] &lt;&lt; " ";
        }
        cout &lt;&lt; endl;
    }
    return 0;
}
I don't have time to do a style review at the moment, so until I can expand on this later, I'll just suggest a different algorithm.



Rather than depending on string manipulation and generating more items than you need, just take an arithmetic approach.

In particular, you can take a deque of ints and add 1 to it until it is equal to the max value.

std::deque&lt; std::deque&lt;int&gt; &gt; results;
std::deque&lt;int&gt; min(Y, 1);
std::deque&lt;int&gt; max(Y, X);
for (; min != max; min = increment(min, Y)) {
    results.push_back(min);
}
results.push_back(max);


As a bit more explanation, a std::deque&lt;unsigned int&gt; is frequently used as a make-shift arbitrary precision integer. The way this is done is to have a sign flag, and then to see each element of the deque as part of a radix = std::numeric_limits&lt;unsigned int&gt;::max() number.

As a concrete example, a std::deque&lt;unsigned char&gt; d = {95, 14, 230} would represent 95 * 255^2 + 14 * 255^1 + 230 * 255^0 in the same way common base ten 134 = 1 * 10^2 + 3 * 10^2 + 4 * 10^0.

Anyway, I'm getting carried away with this. 

What you're in need of is a much more specific case of this. Rather than making a generic adder, all you have to do is just add 1, and if that causes the lowest digit to overflow, push it back down to a 1 and carry the add up the chain.

std::deque&lt;int&gt; increment(std::deque&lt;int&gt; d, int Y)
{
    bool carry = true;
    for (std::deque&lt;int&gt;::reverse_iterator it = d.rbegin(), end = d.rend(); it != end; ++it) {
        *it += 1;
        if (*it &gt; Y) {
            *it = 1;
        } else {
            carry = false;
        }
    }
    if (carry) {
        d.push_front(1);
    }
    return d;
}   


The above code is untested and unoptimized. It can probably be written more compactly, but it's been a long time since I've done anything like this, and I'm just trying to illustrate how it can be done arithmetically. 

Also, if you're concerned about performance, you might want to have increment mutate d rather than return a modified copy.