C - 按字典顺序排列的递归排列

Question

我正在尝试对最多 8 个字符的字符串进行排列。问题是它必须使用递归来完成，并且必须按字典顺序排列。我找到了一个递归解决方案，但它最多只能用于 4 个字符。在那之后，它又开始搞砸了。

void swap(char* a, char* b){
    char temp = *a;
    *a = *b;
    *b = temp;
}
void recursion(char* arr, int start, int n){
    if (start == (n-1)){
        printf("%sn", arr);
        return;
    }
    for (int i = start; i < n; i++){
        recursion(arr, start+1, n);
        swap(arr+start+1, arr+n-1);
        int j = start+1;
        while (j < n && arr[start] > arr[j]){
            j++;
        }
        if (j >= n){
            continue;
        }
        swap(arr+start, arr+j);
    }
    swap(arr+start+1, arr+n-1);
}
int main(int argc, char *argv[]) {
    char arr[9];
    char charakter;
    int m = 0;
    while (scanf("%c", &charakter) != EOF){
        if (charakter == 'n'){
            break;
        }
        else if (isalpha(charakter) || isdigit(charakter)){
            arr[m] = charakter;
            m++;
        }
        else{
            fprintf(stderr, "Error!n");
            return 100;
        }        
    }
    arr[m] = '';
    int n = strlen(arr);
    int start = 0;
    recursion(arr, start, n);
    return 0;
}

知道如何修复递归函数吗？

Answer 1

你的解决方案很奇怪，看看这里和这里一个修复：

void recursion(char *arr, int start, int n) {
  if (start == n) {
    printf("%sn", arr);
    return;
  }
  for (int i = start; i < n; i++) {
    swap(arr + start, arr + i);
    recursion(arr, start + 1, n);
    swap(arr + start, arr + i);
  }
}

这里有一个合适的解决方案：

#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
static void recursion(char *str, size_t n, size_t max) {
  if (n < max) {
    recursion(str, n + 1, max);
    for (size_t i = n + 1; i < max; i++) {
      char tmp = str[i];
      str[i] = str[n];
      str[n] = tmp;
      recursion(str, n + 1, max);
      str[n] = str[i];
      str[i] = tmp;
    }
  } else {
    printf("%sn", str);
  }
}
int main(void) {
  char str[42];
  errno = 0;
  if (scanf("%41s", str) != 1) {
    if (errno != 0) {
      perror("scanf()");
    } else {
      fprintf(stderr, "no input");
    }
    return 1;
  }
  recursion(str, 0, strlen(str));
}