递归 C++组合学：不确定如何按顺序获得结果

发布于 2024-10-22 13:49:08 字数 637 浏览 8 评论 0原文

我有一个函数可以打印从长度 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,...等等...

如果不将它们加载到数组/列表中并使用排序算法，有没有办法做这个吗？

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

坚持沉默 2024-10-29 13:49:08

请注意，所有相同长度的字符串都已处于正确的顺序。您给出的示例根本不是按字典顺序排列的，而是按长度排序的。 字典顺序（即字典排序）是您已经看到的。

要获取按长度排序的结果，请首先按长度迭代，并仅生成所需长度的字符串：

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

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

回复收藏 0 原文

忆离笙 2024-10-29 13:49:08

这应该有效：

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

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

回复收藏 0 原文

~没有更多了~