暴力枚举（brute force）指的是枚举所有可能的情况并一一检验的方法。

在不优化的情况下，暴力枚举的时间复杂度通常是指数级。

基本枚举

枚举全排列

以 4 个数为例，4 个数的全排列有 24 种，按字典序排列如下：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

思想

枚举字典序的下一个全排列时，我们当然想贪心地尽可能找靠右边的，这样“增量”小。

但是，如果排列的某一个后缀是降序的，说明这里作为一个子排列已经极大，不能再找更大字典序了。所以，我们需要找到最末的升序对。

找到最后升序对 a_i < a_{i + 1} 后，根据贪心原则，我们只寻找后缀 a_i, a_{i + 1}, \dots, a_n 里的下一个排列。此时 a_i 必须增大一位，增大到哪里呢？显然就是增大到大于 a_i 的最小数。于是，我们将 a_i 和大于 a_i 的最小数 a_k 交换位置。

交换完位置后，a_i（原来的 a_k 固定了），我们需要将剩下的数放进后面的空位 a_{i + 1}, \dots, a_n，显然升序是字典序最小的排列，所以我们把这些数按升序填进去。

算法

我们可以尝试从当前全排列转移到字典序上的下一个全排列，算法如下：

• 寻找最后一个相邻升序对 a_i < a_{i + 1}，若找不到，则说明已经是最后一个排列；
• 寻找 a_{i + 1}, \dots, a_n 中大于 a_i 的最后一个数 a_k；
• 交换 a_i 和 a_k；
• 对 a_{i + 1}, \dots, a_n 升序排序。由于 a_{i + 1}, \dots, a_n 此时一定降序，这个过程可以翻转实现。

这一算法对应 STL 中的 next_permutation 函数。

时间复杂度

单次运行的最坏复杂度为 O(n)，但是平均复杂度是常数 O(1)。

证明：算法的时间复杂度取决于最后升序对的出现位置，也就是取决于排列的最长降序后缀。如果最长降序后缀为 L，则 next_permutation 的时间复杂度为 O(L)。

降序后缀长度大于等于 L!，要求最后的 L 个元素降序排列，由消序法得到情况数是 n! / L!。而后缀长为 L 时时间复杂度为 O(L)，可以分摊给大于等于 1, 2, \dots, L 的后缀一个 O(1)，因此运行 n! 次，总的复杂度就是：

而由微积分，有

所以 T(n) = O(1) \cdot n!，即平均时间复杂度为 O(1)。

实现

bool next_permutation(int *a, const int n) {
	int i;
	for (i = n - 2; i >= 0; i--)
	{
		if (a[i] < a[i + 1])
		{
			break;
		}
	}
	if (i == -1)
	{
		return false;
	}
	int k;
	for (k = n - 1; k > i; k--)
	{
		if (a[k] > a[i])
		{
			break;
		}
	}
	swap(a[i], a[k]);
	reverse(a + i + 1, a + n);
	return true;
}

这一函数的调用将使用 do-while 循环：

int main()
{
    do {
        for (size_t i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        cout << "\n";
    } while (next_permutation(a, n));
}

STL

在 STL 中，std::next_permutation 有相似的实现，通过传入首尾指针实现排序。

枚举组合

枚举从 n 个元素选 r 个的全部组合情况。

例如，从 5 个元素中选 3 个一共有以下情况：

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

算法流程为：

• 从后往前数，找到第一个满足 a_i \ne n - r + i 的位置 i，若找不到，则说明已经是最后一个组合；
• 令 a_i 自增 1；
• 对 j \in \{i + 1, i + 2, \dots, r\}，令 a_j = a_{j - 1} + 1。