5
\$\begingroup\$

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<deque<int> > 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 <iostream>
#include <sstream>
#include <deque>

using namespace std;

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

// The actual function
deque<deque<int> > allPossibleProcedures(int values, int depth) {
    deque<deque<int> > result;
    // I create a start point and an end point for my counting
    string minString; for (int d = 0; d < depth; ++d) { minString.append("1"); }
    string limitString; for (int d = 0; d < depth; ++d) { limitString.append(convert<string>(values)); }
    int start = convert<int>(minString);
    int limit = convert<int>(limitString);
    // I begin counting
    for (int i = start; i <= limit; ++i) {
        deque<int> procedure;
        string text = convert<string>(i);
        bool ok = true;
        for (int c = 0; c < text.length() && ok; ++c) {
            int x = convert<int>(text.at(c));
            if (x <= values && x > 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<deque<int> >procedures = allPossibleProcedures(3,3);
    for (int i = 0; i < procedures.size(); ++i) {
        for (int j = 0; j < procedures[i].size(); ++j) {
            cout << procedures[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
\$\endgroup\$
4
\$\begingroup\$

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

As a concrete example, a std::deque<unsigned char> 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<int> increment(std::deque<int> d, int Y)
{
    bool carry = true;
    for (std::deque<int>::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.

\$\endgroup\$
  • \$\begingroup\$ Hello Corbin. I tested your code, but (3,3) gave me pastebin.com/neUny5N8 - I don't fully understand why. \$\endgroup\$ – Omega Apr 23 '13 at 2:00
  • \$\begingroup\$ @Omega Whoops, will edit my answer in a bit, but for now, change the ` min <= max` to min != max and then after the loop add results.push_back(max). Got overzealous and forgot that lexicographical ordering will not work here since 1111 is considered lexicographically less than 333. \$\endgroup\$ – Corbin Apr 23 '13 at 3:12
  • \$\begingroup\$ I believe that now I get 111, 222, and 333. Hmm. \$\endgroup\$ – Omega Apr 23 '13 at 3:19
  • \$\begingroup\$ Ok, I'm not sure what the problem was, but I based myself on your code and got this working: pastebin.com/DAyc3Bhv - it looks nice, thanks a lot! Now I got to see how to make it faster. \$\endgroup\$ – Omega Apr 23 '13 at 3:59
1
\$\begingroup\$

A question like this is basically crying out for recursion - we know we'll (effectively) need to loop y times from 1 to x. We can encode the loop number in the recursion:

void recurse(std::deque<std::deque<int>>& deq, std::deque<int>& d, 
             int x, int y, int ymax)
{
    if(y == ymax) return;
    for(int i = 1; i <= x; ++i) {
        d[y] = i;
        deq.push_back(d);
        recurse(deq, d, x, y + 1, ymax);   
    }
}

This is relatively safe, because we only recurse to a depth of y. Since the number of elements grows at a rate of y^x, any practical computable value will require y and x to be relatively small.

Unfortunately the above generates some duplicate elements (it could be modified so that it did not). Some sorting and filtering out only unique values will give you what you want, however:

std::deque<std::deque<int>> all_sequences(int x, int y)
{
    std::deque<std::deque<int>> deq;
    std::deque<int> d(y, x);
    recurse(deq, d, x, 0, y);
    std::sort(deq.begin(), deq.end(), [](const std::deque<int>& d1, 
                                         const std::deque<int>& d2) 
                                         { return d1 < d2; });
    auto it = std::unique(deq.begin(), deq.end());
    deq.resize(std::distance(deq.begin(), it));
    return deq;
}
\$\endgroup\$
  • \$\begingroup\$ Perhaps our brains just latched onto this in different ways, but I don't think this cries out for recursion at all. Your explanation of the recursion is practically explaining a loop transformed into recursion. To each his own, though, I suppose :). \$\endgroup\$ – Corbin Apr 22 '13 at 7:24
  • \$\begingroup\$ @Corbin Yeah, it's more of a "to my mind ...". When I see a problem like this I immediately start looking for a recursive solution, but that may just be me. \$\endgroup\$ – Yuushi Apr 22 '13 at 8:00
1
\$\begingroup\$

Say X = 3 and Y = 3, then the combination is:

So basically, you have a:

min number which is 111

max number which is 333

so:

  • calculate min number which is = the number 1 repeated Y times.

  • calculate max number which is = the number X repeated Y times.

  • you start with min number

  • if last digit is < X, add 1

  • if last digit is = X, add (11 - X)
  • if second from last digit is = X, add 100 to min
  • repeat last three steps until the number you have is equal to max.

This is the basic idea, you might need to tweak it a bit as the numbers get higher.

\$\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.