Рекурсивная C ++ комбинаторика: не уверен, как привести результаты в порядок

Question

У меня есть функция для печати всех комбинаций троичных строк от длины 0 до длины 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;
}

Однако я не совсем уверен, как получить их в логическом порядке.Например, результаты получаются следующим образом, когда я вызываю 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 * 100 *хотели бы, чтобы они вышли в лексикографическом порядке, например: 0,1,2,00,01,02,10,11,12,20,21,22, и т. д. *

Беззагружая их в массив / список и используя алгоритм сортировки, есть ли способ сделать это?

Answer 1

Обратите внимание, что все строки одинаковой длины уже находятся в правильном порядке. И приведенный вами пример вовсе не является лексикографическим порядком, он упорядочен по длине. Лексикографический порядок (то есть сортировка по словарю) - это то, что вы уже видите.

Чтобы получить результаты, отсортированные по длине, сначала выполните итерацию по длине и создайте только строки нужной длины:

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 += '-';
     }
}

демо

Answer 2

Это должно работать:

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");
    }
}