Recursive C++ Combinatorics: Not sure how to get the results in order

I have a function to print all of the ternary string combinations from length 0 to length n:

void TerString(int len,string input){
    printf("\n%s",input.c_str());
    if (input.length()<len){
        TerString(len,input+"0");
        TerString(len,input+"1");
        TerString(len,input+"2");
        return;
    }
    else
    return;
}

However, I'm not entirely sure how to go about getting these in a logical order. For example, the results come out like this when I invoke TerString(3,""): 0,00,000,001,002,01,010,011,012,02,020,021,022,1,10,100,101,102,11,110,111,112,12,120,121,122,2,20,200,201,202,21,210,211,212,22,220,221,222

I would like them to come out in lexicographical order like this: 0,1,2开发者_运维百科,00,01,02,10,11,12,20,21,22,...etc...

Without loading them into an array/list and using a sort algorithm, is there a way to do this?

Note that all the strings of the same length are already in the right order. And the example you gave isn't lexicographical order at all, it's ordered by length. Lexicographical order (i.e. dictionary sort) is what you're already seeing.

To get results sorted by length, iterate by length first, and generate only strings of the desired length:

void TerStringHelper( size_t pos, string& input )
{
    if (pos >= input.size())
        cout << input << endl;
    else
        for( input[pos] = '0'; input[pos] < '3'; input[pos]++ )
            TerStringHelper(pos+1, input);
}

void TerString( size_t maxlen )
{
     string input = "-";
     while (input.size() <= maxlen) {
         TerStringHelper(0, input);
         input += '-';
     }
}

demo

This should work:

void TerString(int len, string prefix){
    printf("\n%s%s", input.c_str(), "0");
    printf("\n%s%s", input.c_str(), "1");
    printf("\n%s%s", input.c_str(), "2");
    if (--len > 0) {
        TerString(len, input+"0");
        TerString(len, input+"1");
        TerString(len, input+"2");
    }
}