CC++ & Algorithm

排列：排队有顺序

困难11
语言版本：C++Python
概述：排列就像给队伍排座位，谁在前面谁在后面都很重要，用C++可以轻松生成所有可能的排队顺序。

排列：排队有顺序——用C++生成所有可能的顺序

想象一下，你们班要选三位同学拍照，小明、小红和小刚。站成一排时，谁站在左边、谁在中间、谁在右边，每一种不同的站法都会拍出不同的照片。如果小明站左边、小红中间、小刚右边，这是一种；如果小明和小红交换位置，又是一种新的照片。你会发现：顺序不同，结果就不同。这就是排列。

在数学里，排列就是从 n 个不同的人中选出 m 个人，然后按顺序排成一列的方法数。公式是：

P(n,m)=n×(n−1)×⋯×(n−m+1)P(n, m) = n \times (n-1) \times \dots \times (n-m+1)

如果 m = n（也就是把所有人都排进去），就叫全排列。比如三个人全排列有 3×2×1=63 \times 2 \times 1 = 6 种。

在C++里，我们可以用 next_permutation 函数轻松地把所有不同的排列一个个列出来。它像是一个“下一个排队方案”生成器，每次调用都会把数组变成字典序下一个更大的排列（就像把数字从小到大顺序改一下）。下面我们就来详细学习它。

什么是排列？再举几个生活中的例子

  • 排队打饭：5个同学排队，谁先打到饭很重要。不同的队伍顺序，代表了不同的“排列”。
  • 设定密码：数字1、2、3组成的三位数密码，123和132是不同的密码，因为顺序不同。
  • 比赛名次：班级跑步比赛，前三名从1到3号运动员中产生。张三第一、李四第二、王五第三，和换一下名次，就是不同的排列。

把这些例子对应到数学上：从n个不同元素中，取出m个按顺序排列，每个不同的顺序都是一个新的排列。

用C++生成排列——认识 next_permutation

next_permutation 是C++标准库 <algorithm> 里的一个函数。它接收两个迭代器（通常用数组的开始和结束地址），然后原地修改数组，把它变成当前序列的字典序下一个排列。如果当前已经是最后一个排列（比如 {3,2,1}），它会返回 false，并把数组变回最小的排列（升序）。

使用前必须做的两件事：

  1. 包含头文件 #include <algorithm>
  2. 先对数组从小到大排序（因为 next_permutation 从当前顺序开始找下一个，如果一开始不是升序，它会从当前顺序开始，可能会漏掉前面的一些排列。所以习惯做法是先用 sort 排好序，就能得到所有排列）

下面是最基本的全排列代码（保留原有的示例，并加上更多注释）：

#include <iostream>
#include <algorithm> // 提供 next_permutation
using namespace std;

int main() {
    // 定义三个人的编号，1、2、3
    int arr[] = {1, 2, 3};
    int n = 3; // 数组长度

    // 一定要先排序！让数组处于最小排列（升序）
    sort(arr, arr + n);

    cout << "1、2、3 的所有全排列：" << endl;
    do {
        // 输出当前排列
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    } while (next_permutation(arr, arr + n)); // 生成下一个，直到没有下一个

    return 0;
}

运行结果：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

注意：next_permutation 会改变数组内容。如果你还想保留原始数据，可以先复制一份（比如用另一个数组保存原样）。

不止全排列：用 next_permutation 实现“选几个排几个”

有时候我们不需要把所有人全排进去，比如从4个同学中选2个拍照，那么排列数就是 P(4,2)=4×3=12P(4,2) = 4 \times 3 = 12 种。怎么用 next_permutation 得到这12种呢？

技巧：先把所有同学（比如编号1~4）放进数组，然后对数组进行全排列，每次只输出前两个元素。这样，所有不同的前两位顺序就是我们要的排列。因为 next_permutation 会遍历所有 4!=244! = 24 种全排列，其中前两位的每种不同顺序恰好出现一次（因为后两位也在变，但前两位不同顺序已经覆盖了所有可能）。

来看例子：从1,2,3,4中选两个排列。

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

int main() {
    int arr[] = {1, 2, 3, 4}; // 所有同学编号
    int n = 4;
    int m = 2; // 我们要选2个人并排序

    sort(arr, arr + n); // 先排序

    cout << "从1、2、3、4中选2个的排列有：" << endl;
    int count = 0; // 计数
    do {
        // 只输出前m个（即选出来的顺序）
        for (int i = 0; i < m; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        count++;
    } while (next_permutation(arr, arr + n)); // 仍然全排列

    cout << "共 " << count << " 种（实际排列数是 P(4,2) = 4×3 = 12，这里全排列了24次，所以每个前两位重复了？其实没有重复，因为后两位不同，前两位相同的情况不会出现？等一下……）" << endl;

    return 0;
}

运行结果会输出12行吗？我们来分析一下：next_permutation 产生的全排列共有24个，每个排列的前两位是否可能相同？例如排列 1,2,3,4 和 1,2,4,3 的前两位都是 1 2，所以这里就会出现重复的 1 2。所以这种方法不能直接得到所有不重复的部分排列，因为后两位的交换会导致前两位组合重复出现。正确的做法是：用 next_permutation 只对前m个位置有意义，但我们想要的是从n个不同元素中选m个的所有排列（不重复）。这通常需要用递归或对组合结果再排列。所以在八级阶段，我们通常只介绍全排列。如果想学习部分排列，可以看后面“相关指引”里的递归方法。

⚠️ 常见误解：直接用 next_permutation 全排列然后取前m个，会得到重复的（前m个相同但后m~n个不同），所以不要用这个方法求部分排列。部分排列需要用其他方法（如 next_permutation 配合 do...while 只输出前m个但跳过重复？实际上无法简单跳过）。记住：next_permutation 只适合求全排列。

新手容易犯的错误

  1. 忘记先排序：如果数组一开始不是升序，next_permutation 会从当前顺序开始生成，会遗漏掉一些排列。比如 arr = {2,1,3} 时调用，它只会生成从 2,1,3 开始的后续排列，不会生成 1,2,3 和 1,3,2。所以一定要先 sort。

  2. 忘记包含头文件：<algorithm> 里还有 sort、swap 等，不包含会编译错误。

  3. 循环写法错误：要用 do...while 而不是 while，因为要先打印第一个（排序后的）排列。如果用 while 条件判断时先调用 next_permutation，就会跳过第一个排列。

  4. 误以为 next_permutation 会保留原数组：它会修改数组，所以如果你之后还需要原顺序，记得备份一份，比如用 int backup[100]; copy(arr, arr+n, backup);。

  5. 使用 next_permutation 处理字符串：可以用于字符数组，比如 char str[] = "ABC"; 但注意字符串要以 '\0' 结尾，排序也要对字符排（按ASCII码）。

  6. 混淆排列与组合：排列强调顺序，组合不强调顺序。比如选班干部，如果职务不同（班长、副班长）就是排列；如果只选两个人当代表，不分职务，那就是组合。

完整示例：用字符数组模拟“同学排队照相”

我们把同学姓名用字母代替：A、B、C、D，他们要全排列站在一起拍照。代码：

#include <iostream>
#include <algorithm> // 包含 sort 和 next_permutation
using namespace std;

int main() {
    // 四个同学，用字母表示
    char students[] = {'A', 'B', 'C', 'D'};
    int n = 4; // 总人数

    // 先按字母顺序排序（虽然已经是 A,B,C,D，但养成好习惯）
    sort(students, students + n);

    cout << "A、B、C、D 四人拍照的所有站位顺序：" << endl;
    int cnt = 0; // 计数
    do {
        // 输出当前排列
        for (int i = 0; i < n; i++) {
            cout << students[i] << " ";
        }
        cout << endl;
        cnt++;
    } while (next_permutation(students, students + n));

    cout << "一共有 " << cnt << " 种排列（全排列数 = 4! = 24）。" << endl;

    return 0;
}

运行结果会列出24行，从 A B C D 到 D C B A。

相关指引

  • prev_permutation：与 next_permutation 相反，生成字典序上一个排列。如果当前是最小排列，返回 false 并变成最大排列。
  • 递归生成排列：对于初学者，了解 next_permutation 就够用了；如果想深入学习，可以自己写递归函数——从第一个位置开始，依次选一个没选过的元素，然后递归选下一个。这样更灵活，也能处理部分排列。
  • 组合（没有顺序）：如果你只关心选哪几个人，不关心谁前谁后，那就是组合。可以用 “二进制枚举” 或 next_combination（标准库没有，需要自己实现）。
  • 阶乘与排列数计算：P(n,m) = n! / (n-m)!，可以用循环或 tgamma 函数计算。

掌握了排列，你就打开了C++中“枚举所有可能性”的一扇门，在解决很多搜索问题、穷举问题时会非常有用。

例题精讲

1单选题

以下哪个问题属于排列问题？

A从5名学生中选3人参加比赛
B从5名学生中选3人排成一排照相
C从5名学生中选3人担任班干部（无区别）
D从5名学生中选3人进行面试（不考虑顺序）
2判断题

从4个不同元素中取出4个进行排列，排列数为24。

3填空题
以下C++代码使用next_permutation输出数组{1,2,3}的所有全排列，请补全循环条件。

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int arr[] = {1,2,3};
    do {
        for(int i=0;i<3;i++) cout<<arr[i]<<" ";
        cout<<endl;
    } while( ___ );
    return 0;
}
4单选题

从6个不同元素中取出2个进行排列，有多少种不同的排列方式？

A30
B36
C15
D12
5判断题

C++中next_permutation函数会生成当前排列的下一个字典序排列，如果当前排列已经是最后一个排列，则返回false并将数组变为第一个排列。