C++算法初级4——排列枚举

排列枚举

1. 引入

举例 ：取宝石问题

假设在一个大房间有nn个宝石，每一处宝石用一个坐标(x, y)(x,y)表示。如果你从任意一处宝石的地方出发，依次经过每个放宝石的地方并取走宝石，最终要求回到出发地点，问最短需要走的距离是多少。

在这个情境里，经过不同地点的顺序会改变最终的行走距离。所以，我们要枚举的就是经过1~n一共n个位置的顺序。

举例 ：八皇后问题

著名的八皇后问题，在8x8的棋盘上放8个皇后，要求每个皇后不能在同一行，不能再同一列，也不能在同一条对角线上。如下面两种摆法就是不允许的：

如下图就是一个合法的解：
在这个例子中，由题意可以推出，每一行只能放一个皇后，且每一列只能放一个皇后。如果我们把列看成数组的下标，行看成数组里的值的话，如下图所示

可以看到，该实例用数组表示就是：

int a[10] = {0, 5, 7, 1, 4, 2, 8, 6, 3};	
// 这里我们从1开始存储，0号无意义。
1
2

所以，我们就把八皇后问题转换成如下问题：

寻找一个1~n的排列，使得它满足八皇后问题中的对角线限制。

因为我们会在讲述递归和深度优先搜索的时候着重解释“八皇后问题”，并不会在这里对该问题做过多展开，感兴趣的同学可以自行思考一下“对角线限制”应该如何用数学形式规范表示。

在上面的“取宝石问题”和“八皇后问题”中，我们都想寻找满足某个条件的排列。这里，我们试图用最简单的枚举法来解决这个问题。回顾一下枚举的基本思路：
确定枚举对象、枚举范围和判定条件；
枚举可能的解，验证是否是问题的解。

代入到题目中的情景，就是

• 枚举所有排列；
• 检查每一个排列是否满足要求；

下面，我们要介绍一下如何枚举所有1~n的排列。

2. 排列的表示方式

上面我们用“1~n”的顺序来描述的n个对象中的某种排序关系，其实有个专业术语叫排列。

其中，最简单的对排列的解释就是：将n个元素按照一定的顺序排成一列，即为n个数的排列。
上面列举了几个需要找到合法排列的例子之后，下面我们将介绍如何枚举所有的排列。

和子集枚举一样，在设计枚举算法之前，我们也要首先确定排列在计算机里的表示方式。

这里，我们似乎只能想到用数组来存储排列，如下方代码所示：

int a[10] = {1, 2, 3, 4, 5, 6};   // 原序列
int b[10] = {2, 3, 1, 5, 4, 6};   // 原序列的一种排列
1
2

这意味着，我们将对一个数组的对象进行枚举。在这里，我们需要明确两个问题：

1. 我们按什么顺序枚举？

这里，我们引入字典序的概念，并且最终按照字典序的顺序枚举排列。字典序，又叫字母序，是规定两个序列比较大小的一种方式。其规则是对于两个序列a和b：

从第一个字母开始比较，如果在第i个位置满足，i没有超过两个序列的长度，小于i处两个序列对应位置的元素都相等，而第i位两个序列对应位置元素不等的话，则若a[i] < b[i]，那么序列a小于序列b，否则序列b小于序列a。
若从第一个位置直到其中一个序列的最后一个位置都相等的话，则比较a和b的长度，若a的长度小于b，则序列a小于序列b（此时a是b的前缀），而如果b序列的长度小于a，那么序列b小于序列a。
若两个序列长度相等，并且所有元素相等，则序列a等于序列b。

2. 如何生成下一个排列的数组？
   C++标准模板库（STL）里面已经有现成的实现了

标准模板库（Standard Template Library, STL） 是惠普实验室开发的一系列软件.它分为算法（algorithm）、容器（container）和迭代器（iterator）三个部分，实现了代码开发中常用的算法（如求最小值最大值、排序、二分查找等）和数据结构（如向量vector、集合set、映射map等）。

之所以叫做“模板库”，是因为在STL中几乎所有代码都是用模板类或者模板函数的方式实现的。

比如说我们常用的函数min(a, b)、max(a, b)以及swap(a, b)就是在算法部分实现的。

可以发现对于不同的数据类型，包括整数（int）、浮点数（double），甚至自己定义的类对象，都可以调用swap函数。这就是模板的好处。

next_permutation 函数是STL的算法部分实现的一个函数，其功能是将数组中存储的元素重新排列到字典序更大的排列。
在我们考虑排列的字典序时，因为所有排列长度相同，所以只需要比较对应位置元素大小即可

next_permutation函数有3个参数，分别代表头指针，尾指针和比较函数。

头指针和尾指针：表示该函数需要重新排列的范围是头指针到尾指针之间的所有元素，包括头指针指向的元素，不包括尾指针指向的元素。
比较函数：这是一个可选参数，用于指定数组中存储对象的大小关系。

之所以需要比较函数，是因为只有存在单个元素的大小关系，才可以定义字典序。 对于整数、浮点数以及字符数组，因为整数、浮点数和字符的大小关系已经在C++里面定义过了，所以不需要传比较函数。当需要对自定义的类对象数组进行重排时，可能需要传入比较函数。

【返回值】
next_permutation 的返回值表示是否存在字典序更大的排列。
如果存在，返回true，否则返回false。但是即便不存在字典序最大的排列，调用该函数也会导致数组a中的元素被重排成字典序最小的一个，例如：

int a[10] = {4, 3, 2, 1};
if (next_permutation(a, a + 4)) {
    cout << "Yes" << endl;
} else {
    cout << "No" << endl;
}
for (int i = 0; i < 4; ++i) cout << a[i] << ' ';
cout << endl;
1
2
3
4
5
6
7
8

这段代码的输出结果是

No
1 2 3 4
1
2

3. “取宝石问题”的代码实现

取宝石问题

假设在一个大房间有n个宝石，每一处宝石用一个坐标(x, y)表示。如果你从任意一处宝石的地方出发，依次经过每个放宝石的地方并取走宝石，最终要求回到出发地点，问最短需要走的距离是多少。

在这个情境里，经过不同地点的顺序会改变最终的行走距离。所以，我们要枚举的就是经过1~n一共n个位置的顺序。

用next_permutation函数解决“取宝石问题”
因为要用枚举法解决第一个问题，所以，代入到题目的情境中，我们可以设计如下算法：

1. 枚举所有n个点的排列
2. 维护最短距离。检查新枚举的排列产生的行走距离是否比之前的最短距离还短。如果短，就更新答案。

#include 
#define N 15
using namespace std;
int n, id[N];
double x[N], y[N];

// 求两个点(x_1, y_1)和(x_2, y_2)之间的直线距离
double dis(double x_1, double y_1, double x_2, double y_2) {
    double dx = x_1 - x_2;
    double dy = y_1 - y_2;
    return sqrt(dx * dx + dy * dy);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        id[i] = i;	// 因为我们枚举标号的排列，所以要将标号存进数组里
    }
    
    double ans = -1;    // 因为最开始ans中没有值，所以我们可以将其设置为一个不合法的值	
    // 用do...while循环是为了防止第一次调用时数组id中的值已经被重排
    // 所以会导致标号为1, 2, ..., n的排列没有被计算。
    do {
        // 求解按照id[1], id[2], ..., id[n], id[1]作为行走路线的总距离。
        double cur = dis(x[id[1]], y[id[1]], x[id[n]], y[id[n]]);
        for (int i = 1; i < n; ++i)
            cur += dis(x[id[i]], y[id[i]], x[id[i + 1]], y[id[i + 1]]);
        
        // 如果当前路线的总距离小于之前最优解，就更新。
        if (ans < 0 || cur < ans) ans = cur;
    } while (next_permutation(id + 1, id + n + 1));	
    
    // 输出答案，这里因为是浮点数，所以我们设置精度为4。
    cout << setprecision(4) << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

复杂度分析

这里我们给出右侧使用next_permutation函数枚举排列代码的复杂度分析：

do while 循环的循环次数，也就是长度为n的排列个数为n!。

调用next_permutation函数一次的复杂度为O(n)

所以枚举排列的复杂度为$O(n!\times n)$。

但是如果对于不同元素的排列，如果连续调用next_permutation函数的话，均摊复杂度为O(1)。下面引用的话来自于 stack overflow。

The complexity of std::next_permutation that transforms the permutation to the next permutation in the lexicographic order is O(n) in the worst case.

The number of permutations of n distinct elements is n!. The number of permutations of multisets is n!/(n1!n2!…*nk!) where ni is the number of equal elements of type i.

We have two different cases:

Distinct numbers (set).

next_permutation is often (if not always) implemented with O(1) amortized time when all elements are distinct. The latter means that next_permutation will have O(1) average time when calling many times consequently.

In this scenario, the complexity of your permutationSort function is O(n!) in the worst-case scenario because of n! loop iterations with the amortized O(1) call of next_permutation.

Numbers with repetitions (multiset)

In this case, next_permutation has no guaranteed O(1) amortized complexity, but the number of ‘permutations of multiset’ could be much less than n!. The upper bound of the permutationSort function complexity is O(n!*n) in the worst case. I suppose it can be reduced to O(n!) but don’t know how to prove this fact.

由上面的分析，单纯枚举排列的复杂度是$O(n!)$。

但如果是针对上面解决“取宝石问题”的代码，do while循环中还是有一个for循环枚举，该for循环会循环n次，所以对于“取宝石问题”，复杂度仍是$O(n!\times n)$。

4. 递归枚举排列

我们也可以用递归实现对所有排列的枚举，其本质是分情况讨论。

下图是关于排列的分情况讨论树形图，最下面一层就是所有可能的排列，可以看到，每一条向下延伸的边表示的是下一个可能放置的数字。

并且在所有生成的排列里，靠左边的位置字典序更小，靠右边的位置字典序更大。