用C语言生成长度不超过N的所有字符串

Question

我曾尝试自己编写代码，但失败了。这基本上是我想要的：

a
b
...
z
aa
ba
...
za
ab
bb
...
zz
aaa
baa
...
zzz

最终应该生成所有长度小于N个字符且字符集为a-z的字符串。因此，我不是在寻找排列（互联网上可以找到1001个实现），而是寻找带有替换的组合（至少在Python中是这样称呼的）。顺序不重要，速度要快。

- orlp

---

你的说明不够具体。就像你生成了“baa”一样，你是否也可以生成“aba”、“abb”和“aab”？ - John Feminella

Answer 1

看起来你想用C语言实现，这里是一种方法：

#include <stdlib.h>
#include <stdio.h>

int inc(char *c){
    if(c[0]==0) return 0;
    if(c[0]=='z'){
        c[0]='a';
        return inc(c+sizeof(char));
    }   
    c[0]++;
    return 1;
}

int main(void){
    int n = 3;
    int i,j;
    char *c = malloc((n+1)*sizeof(char));
    for(i=1;i<=n;i++){
        for(j=0;j<i;j++) c[j]='a';
        c[i]=0;
        do {
            printf("%s\n",c);
        } while(inc(c));
    }
    free(c);
}

- Jules Olléon

---

这几乎是完美的，只是跳过了第一次迭代（a，aa，aaa）。将 while(inc(c)) 更改为 do ... while (); 循环即可解决。在这里没有使用 malloc 的理由，因为我不会保留兆字节（更不用说我们不应该在 C 中强制转换 malloc 了）。除了这些小细节之外，享受你的被接受的答案和 +1 :) - orlp

好的，我修复了do-while的问题。至于强制转换malloc，那可能是因为我用一些旧风格的编译器学习C语言时出现了警告... - Jules Olléon

请注意，sizeof(char)的定义始终为1。这意味着inc(c + sizeof(char))可以正确工作，但看起来不正确，因为指针算术已经以相应类型的单位完成。 - Arkku

Answer 2

类似这样（伪代码）：

void CompWithRep(string line,int N) {
  char c;
  if (N==0) return;
  for (c = 'a' ; c <= 'z' ; c++ )
  {
    printf(line + c);
    CompWithRep(line + c,N-1);
  }
}

- Yochai Timmer

---

@Yochai，请仔细研究这行代码 for (c = 'a' ; c < 26 ; c++ ) 并查阅 ASCII表。 - orlp

@Yochai：我认为@nightcracker的意思是你应该有for(c='a'; c < 26+'a'; c++) - David Weiser

是的，已将其更正为<= 'z'，只是以一种伪代码的形式提供了一个通用解决方案，没想到每个人都会修复每一行。我相信你也无法在C中像那样连接字符串，如果有人想提一下的话... - Yochai Timmer

取决于实现。显然会发生完全相同数量的迭代，这里只有一个对函数的调用，在Apalala的想法中，您需要将数字解析回字母，这是每次迭代上另一个O(N)操作。 - Yochai Timmer

@Yochai Timmer：不是在C语言中，使用strcat()函数构建数字的效率远不如使用基于26进制计数器的方法。 - orlp