遞歸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

我會像他們這樣按字典順序排列出來： 0,1,2,00,01,02,10,11,12,20,21,22，...等等...

沒有加載它們到一個數組/列表和使用排序算法，有沒有辦法做到這一點？

Answer 1

注意，相同長度的所有字符串已經在正確的順序。你給的例子並不是字典命令，它按長度排序。 Lexicographical順序（即字典排序）就是你已經看到的。

要獲得按長度排序結果，首先由長迭代，並生成所需長度的字符串只：

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

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