关于按照字典序输出前n个正整数的全排列的问题
本帖最后由 Suud 于 2023-5-10 01:10 编辑题目的要求是：
输入一个正整数n，按照字典序输出从1到n的所有正整数的全排列
比如输入3，输出结果应为：
123
132
213
231
312
321
我写的代码是这样的：
#include <stdio.h>
void fp(int a[], int s, int e);
void change(int a[], int i, int j);
void sort(int a[], int m, int n);
int main()
{
int i, n;
printf("输入: ");
scanf("%d", &n);
int a;
for (i = 0; i < n; i++)
a = i + 1;
fp(a, 0, n);
return 0;
}
void fp(int a[], int s, int n)
{
int i, j;
if (s == n - 1)
{
for (i = 0; i < n; i++)
printf("%d", a);
putchar('\n');
}
else
for (i = s; i < n; i++)
{
change(a, s, i);
sort(a, s + 1, n);
fp(a, s + 1, n);
change(a, i, s);
}
}
void change(int a[], int i, int j)
{
int temp = a;
a = a;
a = temp;
}
void sort(int a[], int m, int n)
{
int i, j, temp;
for (i = m; i < n; i++)
{
for (j = m; j < n - i; j++)
if (a > a)
{
temp = a;
a = a;
a = temp;
}
}
}
但是当我输入为4或者更大的数字的时候，就会出现错误
比如输入4的结果是这样的：
1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3124
3142
3214
3241
3421
3412
4123
4132
4213
4231
4321
4312
1423和1432的顺序错了，包括下面的2413和2431，3412和3421，4312和4321的顺序也反了
包括输入更大的数字的时候也会出现这样的错误
我感觉是sort函数出了问题，但是又不知道具体是为什么 问题出在sort函数中，当j取到n-i-1时，a的值已经超出了数组a的范围。因此可以将循环条件改为j<n-i，即可解决问题。
修改后的sort函数代码如下：
void sort(int a[], int m, int n)
{
int i, j, temp;
for (i = m; i < n; i++)
{
for (j = m; j < n - i; j++)
if (a > a)
{
temp = a;
a = a;
a = temp;
}
}
}
另外，由于sort函数只是对a到a进行排序，因此可以将sort函数中的循环条件改为j<n，即可提高效率。 本帖最后由 Suud 于 2023-5-9 20:49 编辑
isdkz 发表于 2023-5-9 20:35
问题出在sort函数中，当j取到n-i-1时，a的值已经超出了数组a的范围。因此可以将循环条件改为j a
我的sort函数里的循环条件就是j<n-i啊，不是n-i-1
改成你下面说的j<n貌似也不行
不太明白 本帖最后由 sfqxx 于 2023-5-9 21:22 编辑
在你提供的代码中，sort函数实现使用的是冒泡排序（bubble sort）算法。冒泡排序的思想是不断比较相邻的元素，如果顺序不对就交换位置，这样每轮可以确定一个最大的元素，直到所有元素有序为止。
但是在你的代码中，sort函数实现存在两个问题：
1.循环的范围错误
在第二层循环中，j的取值应该从m到n-i-1，而不是从 m 到 n-i。因为每轮都已经将未排序区间中的最大值排在了已排序区间的末尾，所以未排序区间的长度可以减少1。
2.相邻元素对比次数过多
在内层循环中，j的取值始终从m开始，但是已经将前 m-1 个元素排好序了，这些元素不需要再次比较。对于一个长为n的数组，冒泡排序最多进行n^2次对比操作，效率较低。因此我们可以优化这部分代码，在每一轮循环中记录是否发生了交换操作，如果没有交换，则说明已经有序，可以提前结束排序。
优化后的代码如下：
```c
void sort(int a[], int m, int n)
{
int i, j, temp;
for (i = m; i < n - 1; i++)
{
int swapped = 0; // 是否发生交换
for (j = m; j < n - i - 1; j++)
if (a > a)
{
swap(a, j, j + 1);
swapped = 1;
}
if (!swapped) break; // 如果没有交换，提前退出循环
}
}
```
通过修改sort函数之后，你的代码可以正确地输出1~4的全排列，且在输入较大的数字时也能得到正确结果。
然而，为了更好地理解问题，我们可以举一个例子来强化理解。以输入为4的情况为例，当程序执行到第一个12xx时，在sort函数中，由于j只取到了i+1，即2，因此在这个子序列中，3和4之间的大小关系并未被考虑到。而在后续遍历的过程中，由于后面每一个位置都可以与2交换，因此出现了2413这样的情况。
经过优化后的sort函数可以避免上述问题，并能够正确输出所有的全排列。 sfqxx 发表于 2023-5-9 20:49
在你提供的代码中，sort函数实现使用的是冒泡排序（bubble sort）算法。冒泡排序的思想是不断比较相邻的元 ...
还是不行
题目要求按照字典序输出全排列，也就是说1423应该在1432的前面，同样的2413应该在2431前面
但是这么改的话1423依然在1432后面 Suud 发表于 2023-5-9 21:19
还是不行
题目要求按照字典序输出全排列，也就是说1423应该在1432的前面，同样的2413应该在2431前面
但 ...
针对全排列按照字典序输出的问题，需要更改排序方式，只进行一次冒泡排序是不够的。
可以考虑使用STL的`next_permutation()`函数来进行全排列的生成。
举例如下：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a = {1, 4, 2, 3};
do {
for(int i=0;i<4;i++) cout<<a;
cout<<endl;
} while(next_permutation(a, a+4));
return 0;
}
通过上述代码可以得到{1, 4, 2, 3}的所有全排列并按照字典序输出。 sfqxx 发表于 2023-5-9 21:24
针对全排列按照字典序输出的问题，需要更改排序方式，只进行一次冒泡排序是不够的。
可以考虑使用STL ...
我们老师要求我们自己写出程序，不能用现有的 刚刚把排序方法换成选择排序，然后把fp函数改成这样就行了
void fp(int a[], int s, int n)
{
int i, j;
if (s == n - 1)
{
for (i = 0; i < n; i++)
printf("%d", a);
putchar('\n');
}
else
for (i = s; i < n; i++)
{
swap(a, s, i);
sort(a, s + 1, n);
fp(a, s + 1, n);
sort(a, s + 1, n);
swap(a, i, s);
}
} sfqxx 发表于 2023-5-9 20:49
在你提供的代码中，sort函数实现使用的是冒泡排序（bubble sort）算法。冒泡排序的思想是不断比较相邻的元 ...
感觉冒泡排序我还是没搞明白……
不过我把排序方法换成选择排序，再把fp函数微调了一下，整成8楼那样就可以了
总之还是谢谢 太帅了，兄弟，在这里找到了答案。
页:
[1]