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

Suud

题目的要求是：
输入一个正整数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[n];
    for (i = 0; i < n; i++)
        a[i] = 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[i]);
        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[i];
    a[i] = a[j];
    a[j] = 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[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = 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函数出了问题，但是又不知道具体是为什么

最佳答案

月排行榜 / 总排行榜

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()`函数来进行全排列的生成。

举例如下：

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[4] = {1, 4, 2, 3};
    
    do {
        for(int i=0;i<4;i++) cout<<a[i];
        cout<<endl;
    } while(next_permutation(a, a+4));

    return 0;
}

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

Suud

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

可以考虑使用STL ...

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

Suud

刚刚把排序方法换成选择排序，然后把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[i]);
        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);
        }
}

Suud

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

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

Axiujiu

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