Look for an alternative solution to generate data sequence

Question

I have a problem, say:

Generate a new line from the previous one by one rule.
1, 11, 21, 1211, 111221, 312211, 13112221, ...

• "1": means one number 1, so the next line will be "11"
• "11": means two numbers 1, so the next line will be "21"
• "21": means one number 2 and one number 1, so the next line 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;
}        

, , , STL. std::transform, . ? - ? ! , , .

,
Chan

Answer 1

, "" STL, . , , , std::adjacent_difference, , .

, look_n_say, . , , ostream. , . n , operator <<, . :

• , .
• , , n.

:

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 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 ... */);
}

, . , , , .

Answer 2

. RLE Rosetta Stone, ++. , .

.

Answer 3

STL fancy pants 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);
}