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 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
#include
#include

using namespace std;

// Converts a value to any type
template
T convert(S original) {
stringstream ss; ss > result;
return result;
}

// The actual function
deque > allPossibleProcedures(int values, int depth) {
deque > result;
// I create a start point and an end point for my counting
string minString; for (int d = 0; d (values)); }
int start = convert(minString);
int li

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 > results;
std::deque min(Y, 1);
std::deque 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 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::max() number.

As a concrete example, a std::deque 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 increment(std::deque d, int Y)
{
    bool carry = true;
    for (std::deque::reverse_iterator it = d.rbegin(), end = d.rend(); it != end; ++it) {
        *it += 1;
        if (*it > 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.

StackExchange Code Review Q#25315, answer score: 4