pta7-2 输出全排列c语言

以下是基于C语言实现全排列算法的一种常见方法，采用递归的方式完成： ### 方法描述 通过递归的思想解决全排列问题。核心思想是固定一个位置上的数字，然后对其余部分进行全排列操作。当所有位置都被固定过之后，就得到了所有的排列。 #### 示例代码 ```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 start, int end) { if (start == end) { // 当前到达最后一个字符时打印结果 printf("%s\n", str); } else { for (int i = start; i <= end; ++i) { // 将当前位置与后续每个位置的字符互换 swap(&str[start], &str[i]); // 对剩余的部分继续递归调用 permute(str, start + 1, end); // 还原状态以便尝试其他可能性 swap(&str[start], &str[i]); } } } int main() { char str[] = "123"; // 待排列的字符串 int n = strlen(str); // 字符串长度 printf("All permutations of %s are:\n", str); permute(str, 0, n - 1); // 调用全排列函数 return 0; } ``` --- ### 代码解析 1. **`swap` 函数** 定义了一个简单的 `swap` 函数用于交换数组中的两个元素[^4]。这是为了在每次递归过程中调整不同位置的字符顺序。 2. **`permute` 函数** 使用递归来生成全排列。对于输入字符串 `str` 的每一位，将其与其他位逐一交换，并对剩下的部分再次调用 `permute` 函数直到处理到最后一位为止[^4]。 3. **主程序逻辑** 主程序定义了待排列的字符串 `"123"` 并计算其长度。随后调用了 `permute` 函数以输出所有可能的排列组合。 --- ### 输出示例 假设输入字符串为 `"123"`，运行以上代码会输出以下结果： ``` All permutations of 123 are: 123 132 213 231 321 312 ``` 此代码实现了无重复数字情况下的全排列功能。如果有重复数字，则需要额外引入标记数组或者排序去重机制来避免重复的结果[^2]。 --- ### 去重扩展（针对含重复数字的情况） 如果输入序列中有重复数字，可以通过先对数组排序再利用布尔标志判断是否跳过来去掉重复项。例如修改后的代码如下所示： ```c #include <stdio.h> #include <string.h> #include <stdbool.h> void swap(char *a, char *b) { char temp = *a; *a = *b; *b = temp; } bool shouldSwap(char *str, int start, int current) { for (int i = start; i < current; i++) { if (str[i] == str[current]) { return false; } } return true; } void permuteWithDuplication(char *str, int start, int end) { if (start == end) { printf("%s\n", str); } else { for (int i = start; i <= end; i++) { if (shouldSwap(str, start, i)) { swap(&str[start], &str[i]); permuteWithDuplication(str, start + 1, end); swap(&str[start], &str[i]); // backtrack } } } } int main() { char str[] = "122"; int n = strlen(str); qsort(str, n, sizeof(char), (int (*)(const void *, const void *))strcmp); printf("All unique permutations of %s are:\n", str); permuteWithDuplication(str, 0, n - 1); return 0; } ``` 该版本能够有效去除因重复数字引起的冗余排列[^2]。 ---