[已解决]关于按照字典序输出前n个正整数的全排列的问题

Suud

题目的要求是：
输入一个正整数n，按照字典序输出从1到n的所有正整数的全排列
比如输入3，输出结果应为：
123
132
213
231
312
321

我写的代码是这样的：

1. #include <stdio.h>
   
2. 
   
3. void fp(int a[], int s, int e);
   
4. void change(int a[], int i, int j);
   
5. void sort(int a[], int m, int n);
   
6. 
   
7. int main()
   
8. {
   
9.     int i, n;
   
10.     printf("输入: ");
    
11.     scanf("%d", &n);
    
12.     int a[n];
    
13.     for (i = 0; i < n; i++)
    
14.         a[i] = i + 1;
    
15.     fp(a, 0, n);
    
16. 
    
17.     return 0;
    
18. }
    
19. 
    
20. void fp(int a[], int s, int n)
    
21. {
    
22.     int i, j;
    
23.     if (s == n - 1)
    
24.     {
    
25.         for (i = 0; i < n; i++)
    
26.             printf("%d", a[i]);
    
27.         putchar('\n');
    
28.     }
    
29. 
    
30.     else
    
31.         for (i = s; i < n; i++)
    
32.         {
    
33.             change(a, s, i);
    
34.             sort(a, s + 1, n);
    
35.             fp(a, s + 1, n);
    
36.             change(a, i, s);
    
37.         }
    
38. }
    
39. 
    
40. void change(int a[], int i, int j)
    
41. {
    
42.     int temp = a[i];
    
43.     a[i] = a[j];
    
44.     a[j] = temp;
    
45. }
    
46. 
    
47. void sort(int a[], int m, int n)
    
48. {
    
49.     int i, j, temp;
    
50.     for (i = m; i < n; i++)
    
51.     {
    
52.         for (j = m; j < n - i; j++)
    
53.             if (a[j] > a[j + 1])
    
54.             {
    
55.                 temp = a[j];
    
56.                 a[j] = a[j + 1];
    
57.                 a[j + 1] = temp;
    
58.             }
    
59.     }
    
60. }
    

复制代码

但是当我输入为4或者更大的数字的时候，就会出现错误
比如输入4的结果是这样的：

1. 1234
   
2. 1243
   
3. 1324
   
4. 1342
   
5. 1432
   
6. 1423
   
7. 2134
   
8. 2143
   
9. 2314
   
10. 2341
    
11. 2431
    
12. 2413
    
13. 3124
    
14. 3142
    
15. 3214
    
16. 3241
    
17. 3421
    
18. 3412
    
19. 4123
    
20. 4132
    
21. 4213
    
22. 4231
    
23. 4321
    
24. 4312

复制代码

1423和1432的顺序错了，包括下面的2413和2431，3412和3421，4312和4321的顺序也反了
包括输入更大的数字的时候也会出现这样的错误
我感觉是sort函数出了问题，但是又不知道具体是为什么

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-5-9 20:49:31

在你提供的代码中，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[j] > a[j + 1])
           {
               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函数可以避免上述问题，并能够正确输出所有的全排列。

跳转到最佳答案楼层

isdkz

问题出在sort函数中，当j取到n-i-1时，a[j+1]的值已经超出了数组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[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
    }
}

另外，由于sort函数只是对a[s+1]到a[n-1]进行排序，因此可以将sort函数中的循环条件改为j<n，即可提高效率。

Suud

isdkz 发表于 2023-5-9 20:35
问题出在sort函数中，当j取到n-i-1时，a[j+1]的值已经超出了数组a的范围。因此可以将循环条件改为j a[j + 1 ...

我的sort函数里的循环条件就是j<n-i啊，不是n-i-1
改成你下面说的j<n貌似也不行
不太明白

sfqxx

在你提供的代码中，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[j] > a[j + 1])
           {
               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函数可以避免上述问题，并能够正确输出所有的全排列。

Suud

sfqxx 发表于 2023-5-9 20:49
在你提供的代码中，sort函数实现使用的是冒泡排序（bubble sort）算法。冒泡排序的思想是不断比较相邻的元 ...

还是不行
题目要求按照字典序输出全排列，也就是说1423应该在1432的前面，同样的2413应该在2431前面
但是这么改的话1423依然在1432后面

sfqxx

Suud 发表于 2023-5-9 21:19
还是不行
题目要求按照字典序输出全排列，也就是说1423应该在1432的前面，同样的2413应该在2431前面
但 ...

针对全排列按照字典序输出的问题，需要更改排序方式，只进行一次冒泡排序是不够的。

可以考虑使用STL的`next_permutation()`函数来进行全排列的生成。

举例如下：

1. 
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.     int a[4] = {1, 4, 2, 3};
   
9.    
   
10.     do {
    
11.         for(int i=0;i<4;i++) cout<<a[i];
    
12.         cout<<endl;
    
13.     } while(next_permutation(a, a+4));
    
14. 
    
15.     return 0;
    
16. }

复制代码

通过上述代码可以得到{1, 4, 2, 3}的所有全排列并按照字典序输出。

Suud

sfqxx 发表于 2023-5-9 21:24
针对全排列按照字典序输出的问题，需要更改排序方式，只进行一次冒泡排序是不够的。

可以考虑使用STL ...

我们老师要求我们自己写出程序，不能用现有的

Suud

刚刚把排序方法换成选择排序，然后把fp函数改成这样就行了

1. void fp(int a[], int s, int n)
   
2. {
   
3.     int i, j;
   
4.     if (s == n - 1)
   
5.     {
   
6.         for (i = 0; i < n; i++)
   
7.             printf("%d", a[i]);
   
8.         putchar('\n');
   
9.     }
   
10. 
    
11.     else
    
12.         for (i = s; i < n; i++)
    
13.         {
    
14.             swap(a, s, i);
    
15.             sort(a, s + 1, n);
    
16.             fp(a, s + 1, n);
    
17.             sort(a, s + 1, n);
    
18.             swap(a, i, s);
    
19.         }
    
20. }

复制代码

Suud

sfqxx 发表于 2023-5-9 20:49
在你提供的代码中，sort函数实现使用的是冒泡排序（bubble sort）算法。冒泡排序的思想是不断比较相邻的元 ...

感觉冒泡排序我还是没搞明白……
不过我把排序方法换成选择排序，再把fp函数微调了一下，整成8楼那样就可以了
总之还是谢谢

Axiujiu

太帅了，兄弟，在这里找到了答案。