Look for alternative solution for generating a sequence of data

I have a problem, let's say:

Generate a new string from the previous one following by one rule.

1, 11, 21, 1211, 111221, 312211, 13112221,...

1. "1" : means one number 1 so the next string will be "11"
2. "11" : means two numbers 1 so the next string will be "21"
3. "21" : means one number 2 and one number 1 so the next string will be "1211" ....

And here is my solution:

#include <string>
#include <iostream>

using namespace std;

class look_n_say {
public:
    look_n_say( int n ) : n( n ) {
    }

    friend ostream& operator <<( ostream& out, const look_n_say& rhs ) {
        string result;
        string init_str( "1" );
        out << init_str << endl;
        for( int i = 1; i < rhs.n; ++i ) {
            result = rhs.get_new_str( init_str );   
            out << result << '\n';
            init_str = result;
            result.clear();
        }
        return out;
    }

private:
    string get_new_str( const string& str ) const {
        int cnt( 1 );
        string result;
        for( string::size_type i = 0, len = str.length(); i < len; ++i ) {
            if( i < len - 1 && str[i] == str[i + 1] ) {
                ++cnt;
            }
            else {
                result.append( 1, cnt + 48 );
       开发者_高级运维         result.append( 1, str[i] );
                cnt = 1;
            }
        }
        return result;
    }

private:
    int n;
};

int main() {
    look_n_say lns( 10 );
    cout << lns << endl;
    return 0;
}        

The reason that I'm not satisfied with my solution is that I missed an elegant solution using STL algorithm here. I thought of std::transform, but found no way to apply it. Is there any better way to solve this problem? Can anyone share with me? Any feedback and comments on my coding style would be greatly appreciated! Please tell me how bad my coding style was, and I will learn from that.

Thanks,

Chan

To the best of my knowledge there isn't an STL "one-liner" that can generate this sequence. You could use a combination of algorithms to try to delineate all the ranges of adjacent consecutive values, perhaps using std::adjacent_difference, but I honestly think the hand-written loop will be more elegant.

On an unrelated note, I'm not sure I support your decision to design look_n_say as you have. As you've written the class, you have an object whose only purpose is to write values to an ostream. You can't query for individual values out of the series, nor can you change the number of values that you get back after you've created the object. You also eagerly recompute the first n numbers every time you call operator <<, which can be extremely inefficient. I would advise changing the class to:

1. Cache the previously-generated values so that you can retrieve them later.
2. Allow the user to query any look-and-say number that they want, not just retrieve the first n of them.

One possible design might be like this:

class LookAndSaySeries {
public:
    string getTerm(size_t index) const; // Get the appropriate term of the series.

private:
    /* Previously-retrieved values, marked mutable since getTerm() will modify even
     * though it's a semantically-const operation.
     */
    mutable vector<string> cachedValues; // Values you've handed back before.
    void generateNext() const;
};

string LookAndSaySeries::getTerm(size_t index) const {
     /* Keep generating values until you have enough to satisfy the request. */
     while (index >= cachedValues.size())
         generateNext();

     return cachedValues[index];
}

void LookAndSaySeries::generateNext() const {
     /* ... insert logic here to generate next term ... */
     cachedValues.push_back(/* ... that value ... */);
}

This allows you to easily query individual numbers without recomputing them on each iteration. You can still print the values to a stream, as you did before, but now have a finer-grained control over how the numbers are produced.

The single steps in this algorithm essentially apply a run-length encoding to the previous sequence. There are several solutions for RLE on Rosetta Stone, including one for C++. Perhaps this is worth a glimpse.

However, that solution doesn’t use any fancy standard library algorithms either.

Fancy-pants STL approach:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

typedef std::vector<int> T;

void thingy(const T &v, const int n)
{
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ""));
    std::cout << std::endl;

    if (n > 0)
    {
        T w;
        for (T::const_iterator it = v.begin(); it != v.end(); )
        {
            T::const_iterator it2 = std::find_if(it, v.end(),
                                    std::bind1st(std::not_equal_to<int>(), *it));
            w.push_back(std::distance(it, it2));
            w.push_back(*it);
            it = it2;
        }

        thingy(w, n-1);
    }
}


int main()
{
    T v;
    v.push_back(1);
    thingy(v, 5);
}