输入：
第一行输入整数n（1<=n<=20）
第二行输入长度为n，由字母、数字的字符串；字符串中可能含有重复的字符
输出：
第一行输出所有不同排列的总数num；下边num行分别为这n个字符的num种排列方式。每行只输出一种排列。
样例输入：
4
aac3
*****只能使用C语言，头文件只能使用这些：<stdio.h> <stdlib.h><math.h><string.h><ctype.h>因为其他的我看不懂=-=
整体思路就是利用回溯的思想，也可认为是深度优先搜索
从字符串第一位idx=0开始，每次递归都从s[idx]之后选择一个字符与s[idx]交换
因为可能有重复字符，可使用哈希数组标记当前循环每个字符是否被选择
因为字符范围不超过ASCII码，所以使用128空间的数组足够用来标记了
选择好当前字符s[i]并与s[idx]交换之后，递归调用继续排列下一位s[idx+1]
注意这里要进行回溯，即不选s[i]而选择之后的某个字符交换到s[idx]
所以要将之前的s[i]与s[idx]交换过来，恢复原状，才能循环判断下一个选择
具体代码截图如下：
运行结果如下：
结果正确，望采纳~
附源码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000000 // 排列总数可能很多
int num = 0; // 记录排列总数
char *res[MAXN] = {NULL}; // 指针数组保存排列结果
void swap(char *x, char *y) { // 交换两个字符变量的内容
char ch = *x;
*x = *y;
*y = ch;
}
void perm(char *s, int n, int idx) { // 回溯产生字符串全排列
if (idx == n) { // 已排列到字符串结尾
res[num] = (char *)malloc(sizeof(char) * (n + 1));
//printf("%s\n", s); // 输出当前排列
strcpy(res[num], s); // 保存当前排列
num++; // 排列总数加1
return;
}
int i, hash[128] = {0}; // 哈希数组，标记每个字符是否被选择
for (i = idx; i < n; i++) {
if (hash[s[i]] == 1)
continue; // 跳过已被标记过的重复字符
hash[s[i]] = 1; // 选过的话在数组中标记为1
swap(&s[idx], &s[i]); // 选择s[i]交换到s[idx]
perm(s, n, idx + 1); // 递归，继续s[idx+1]的选择
swap(&s[idx], &s[i]); // 回溯，当前不选择s[i]，而选择其他字符
}
}
int main() {
int n, i;
scanf("%d", &n);
char *s = (char *)malloc(sizeof(char) * (n + 1));
scanf("%s", s);
perm(s, n, 0);
printf("一共有%d种排列:\n", num); // 输出排列总数
for (i = 0; i < num; i++) { // 输出所有排列
printf("%s\n", res[i]);
free(res[i]); // 释放内存空间
}
free(s);
return 0;
}
追问如果要求按照字典序输出所有排列，代码要怎么改呢
追答可先将输入字符串中的各字符按字典序排列好
再进行上述全排列，结果即可按字典序输出所有的排列
排序字符串中各字符的方法有很多，这里给出调用qsort函数的方法
先定义如下cmp函数：
int cmp(const void *a, const void *b) { // 供qsort调用
return *(char *)a - *(char *)b;
} // 按字典序升序排列
再在main函数中scanf("%s", s)语句后添加如下排序语句即可：
qsort(s, n, 1, cmp); // 先将输入的字符串各字符按字典序排列
运行结果如下：
可见已按字典序输出了所有全排列
只把输入的字符串在读入后排序，输出的字符串还不是按照字典序输出的。我发现还需要把你定义的res数组排序后才能按照字典序输出字符串。
比如，输入n = 3, s = "123"，输出的字符串并不是按照字典序输出的，而是这样的：
不好意思，我之前的思路确实有问题，先排序不能保证全排列也是有序的。
直接将全排列后的res指针数组按字典序排列即可。
对应的cmp函数如下：
int cmp(const void *a, const void *b) { // qsort比较函数
char *s1 = *(char **)a, *s2 = *(char **)b; // 先解引用为char*
return strcmp(s1, s2);
} // 指针数组按字典序升序排列
再在main函数中perm(s, n, 0)之后对res数组进行排序：
qsort(res, num, sizeof(char *), cmp); // 字典序升序排列
运行结果如下：
