C语言递归生成字符串全排列输出顺序不符合预期如何修正

你的现有代码生成的全排列不符合预期字典序，核心原因是：交换第f位和第i位字符后，f位之后的子串顺序会被打乱，导致后续生成的排列无法按从小到大的顺序输出。比如输入abc时，当第一位选择字符c，交换后剩余的两位子串是ba而非升序的ab，因此会先输出cba再输出cab，出现顺序颠倒。

我们可以在原有递归逻辑的基础上，新增子串排序逻辑，保证每次递归时f位之后的子串始终保持升序，就能得到符合要求的排列顺序。完整修改后的代码如下：

#include <stdio.h>
#include <string.h>

void troca(char *x, char *y){
  char temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

// 新增：对a数组中l到r的区间做升序排序
void sort_sub(char *a, int l, int r) {
    int i, j;
    for (i = l; i <= r; i++) {
        for (j = i + 1; j <= r; j++) {
            if (a[i] > a[j]) {
                troca(&a[i], &a[j]);
            }
        }
    }
}

void jeitos(char *a, int f, int h){
  int i;
  if (f == h){
    printf("%s\n", a);
  }
  else{
    for (i = f; i <= h; i++){
      troca((a + f), (a + i));
      // 递归前对f之后的子串排序，保证后续排列按升序生成
      sort_sub(a, f + 1, h);
      jeitos(a, f + 1, h);
      troca((a + f), (a + i));
      // 回溯后恢复f之后子串的顺序，避免影响下一轮循环
      sort_sub(a, f + 1, h);
    } 
  }
}

int main(){
  char string[6];
  // 限制输入长度避免缓冲区溢出
  scanf("%5s", string);
  int n = strlen(string);
  // 先对初始字符串排序，保证排列从最小字典序开始生成
  sort_sub(string, 0, n-1);
  jeitos(string, 0, n-1);
  
  return 0;
}

• 如果输入的字符串存在重复字符，可在循环中新增判断：如果当前a[i]和前一个选中的字符相同，直接跳过本轮循环，即可避免输出重复排列
• 若需要处理更长的字符串，可调整string数组的大小，同步修改scanf的长度限制即可

内容的提问来源于stack exchange，提问作者Lucas Vinícius