C语言全排列1002如何实现全排列算法？

C语言实现全排列（1002）

在C语言中实现全排列有几种常见方法,我将介绍两种主要方法：递归法和非递归法（使用库函数）。

递归实现全排列

#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}
void permute(char *str, int l, int r) {
    if (l == r) {
        printf("%s\n", str);
    } else {
        for (int i = l; i <= r; i++) {
            swap(str + l, str + i);
            permute(str, l + 1, r);
            swap(str + l, str + i); // 回溯
        }
    }
}
int main() {
    char str[] = "ABC";
    int n = strlen(str);
    printf("全排列结果:\n");
    permute(str, 0, n - 1);
    return 0;
}

使用标准库函数next_permutation

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}
int next_permutation(char *str) {
    int len = strlen(str);
    int i = len - 2;
    // 找到第一个不满足降序的字符
    while (i >= 0 && str[i] >= str[i + 1]) {
        i--;
    }
    if (i < 0) {
        return 0; // 已经是最后一个排列
    }
    int j = len - 1;
    // 找到第一个大于str[i]的字符
    while (str[j] <= str[i]) {
        j--;
    }
    // 交换
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
    // 反转i+1到末尾的部分
    int left = i + 1;
    int right = len - 1;
    while (left < right) {
        temp = str[left];
        str[left] = str[right];
        str[right] = temp;
        left++;
        right--;
    }
    return 1;
}
int main() {
    char str[] = "ABC";
    int n = strlen(str);
    // 首先排序
    qsort(str, n, sizeof(char), compare);
    printf("全排列结果:\n");
    do {
        printf("%s\n", str);
    } while (next_permutation(str));
    return 0;
}

使用标准库函数（更简单）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}
int main() {
    char str[] = "ABC";
    int n = strlen(str);
    int count = 0;
    // 首先排序
    qsort(str, n, sizeof(char), compare);
    printf("全排列结果:\n");
    do {
        printf("%s\n", str);
        count++;
    } while (next_permutation(str));
    printf("共 %d 种排列\n", count);
    return 0;
}

注意事项

1. 递归方法适用于小规模数据,大规模数据可能导致栈溢出
2. 使用标准库函数的方法更高效且简洁,但需要C99或更高版本支持
3. 对于数字的全排列,可以先转换为字符串处理
4. 如果输入有重复字符,上述方法会产生重复排列，需要额外处理去重

示例输出（对于"ABC"）

ABC
ACB
BAC
BCA
CAB
CBA

代码可以根据需要修改输入字符串来生成不同字符的全排列。