排列枚举

问题引入¶

给定 $n$ 个不同元素，需要枚举它们的所有排列顺序，并对每一种顺序执行某些操作（如计算路径长度、统计方案等）。

举例：有 $3$ 个城市 A、B、C，想要计算访问顺序的成本，需要枚举以下 $6$ 种路线：

\[\begin{cases} A \to B \to C\\ A \to C \to B\\ B \to A \to C\\ B \to C \to A\\ C \to A \to B\\ C \to B \to A \end{cases}\]

排列枚举¶

全排列的数量¶

根据乘法原理，第 $1$ 个位置有 $n$ 种选择，第 $2$ 个位置有 $n-1$ 种选择，$\cdots$，第 $n$ 个位置有 $1$ 种选择，因此总的排列数为：

\[ n\times (n-1)\times (n-2)\times \cdots \times 1 = n! \]

例如 $n=3$ 时共有 $3! = 6$ 种排列。

这揭示了枚举所有排列的复杂度非常之高。

STL 专属函数：next_permutation¶

在 C++ 的 <algorithm> 头文件中，提供了 next_permutation 函数，用于生成当前序列的下一个字典序排列。

bool next_permutation(BidirIt first, BidirIt last);

参数
- [first, last)：双向迭代器区间 $[first, last)$，表示待排列的范围。
- 注意是左闭右开，用法类似于 sort 函数。
返回值
- 若存在 下一个 字典序排列，函数生成下一个排列并返回 true。
- 若已是最大字典序排列，则函数会将序列重置为最小排列，并返回 false。

使用示例

时间复杂度：$O(n!\times n)$

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[15];
    for (int i = 1; i <= n; i++) a[i] = i; // 初始化为字典序最小的排列
    do 
    {
        for (int i = 1; i <= n; i++)
          cout << a[i] << " ";
        cout << "\n";
    } while (next_permutation(a + 1, a + n + 1));
    return 0;
}

首次执行循环时处理最小排列 $1\sim n$。
每次调用 next_permutation 生成下一个排列，并决定是否继续循环。

do - while 循环要点

do {...} while(condition); 保证循环体至少执行一次。
结合 next_permutation，可确保最初排列（最小字典序）也被处理。

例题¶

例题一：吃奶酪¶

题意：一只老鼠从原点 $(0,0)$ 出发，依次吃完 $n$ 块奶酪。每块奶酪位于 $(x_i, y_i)$，要求最小化移动总距离。

思路：

将奶酪编号为 $1\sim n$，起点编号为 $0$（坐标 $(0,0)$）。
初始化序列 a = [1,2,…,n]，使用 do { … } while(next_permutation(a + 1, a + n + 1)); 枚举所有 $n!$ 种访问顺序。
定义 double dis(int i, int j) 的函数，用于计算两个奶酪 $(x_i,y_i)$ 和 $(x_j,y_j)$ 的距离。

double dis(int i, int j) 
{
    double dx = x[i] - x[j], dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

对当前顺序 ($a[1]..a[n]$):
- 初始化 sum = 0。
- 遍历奶酪顺序 $a$，更新 $sum$：
  - 执行 $sum\leftarrow sum+dis(a[i-1],a[i])$。
- 对移动总距离 $sum$ 取 $\min$ 即可。
时间复杂度：$O(n!\times n)$

例题二：火星人¶

题意：给定 $N$ 和 $M$，以及一个长度为 $N$ 的初始排列，代表火星人当前的数。按字典序向后移动 $M$ 步(调用 next_permutation $M$ 次)，输出最终排列。

思路：直接执行 M 次 next_permutation(a + 1, a + N + 1)。

例题三：环游城市¶

题意：$N$ 座城市，旅行时间矩阵 T[N][N]，从城市 $1$ 出发恰好访问所有其他城市一次再返回 $1$，问有多少条路径总时间恰好是 $K$。

思路：

定义 $p[N]$ 维护城市编号，初始化 $p[i]=i$。由于最后还要回到城市 $1$，因此可以设置 $p[n + 1]=1$。

枚举城市 $2\sim N$ 的全排列 $p$。
- 只需要 next_permutation(p + 2, p + n + 1)。注意城市 $1$ 不参与全排列。
对每个排列 $p$ 计算：
初始化 $sum=0$ 用来计算移动总距离。
累加 $T[p[i]][p[i +1]]$ 移动距离。
若 $sum = K$，则 ans++。

例题四：缆车¶

题意：$n$ 名学生排队乘缆车下山，缆车最大承重 $W$，每辆车费用 $1$ 元。第 $i$ 名学生体重 $a_i$。问最少需要支付多少钱。

定义 $p[i]$ 记录学生编号，初始化 $p[i] = i$。

枚举学生的所有可能顺序（全排列）。
对每一种顺序，按顺序依次尝试上车：
- 用变量 $\texttt{sum}$ 累计当前缆车的载重。
- 初始化 $\texttt{sum} = a[\texttt{p}[1]]$，已租车辆数 $\texttt{cnt}=1$。
- 对余下每位学生 $\texttt{p}[i]$：
  - 如果 $\texttt{sum} + a[\texttt{p}[i]] \le W$，则加到当前缆车：$\texttt{sum} \mathrel{+}= a[\texttt{p}[i]]$。
  - 否则另租一辆：$\texttt{cnt} \mathrel{+}= 1,\;\texttt{sum} = a[\texttt{p}[i]]$.
记录所有顺序中最小的 $\texttt{cnt}$。
时间复杂度：枚举 $n!$ 种顺序，每种顺序做 $O(n)$ 装车操作，适合 $n\le10$。

设 $n=3$, $W=100$，体重数组 ${30, 80, 50}$。
枚举顺序 $(30,50,80)$：

第一位 $30$：新车，$\texttt{sum}=30$，$\texttt{cnt}=1$。
第二位 $50$：$30+50\le100$，同车，$\texttt{sum}=80$。
第三位 $80$：$80+80>100$，新车，$\texttt{cnt}=2$，$\texttt{sum}=80$。
最终需要 $2$ 辆缆车。

对所有排列都可做同样计算，取最小 $\texttt{cnt}$ 即为答案。

例题五：[ABC363C] Avoid K Palindrome 2¶

题目需要排列字符串 $s$，且由于 $|s|\leq 10$，因此考虑使用全排列来做。

注意本题样例 $2$ 的字符串 zzyyx，这个字符串一共只有 $30$ 个排列而不是 $5!$ 个。原因在于这里有两个重复的字符 $z,y$。因此正确的全排列个数为 $\dfrac{5!}{2!\times 2!}$。

如果还是沿用之前的做法（先初始化顺序数组 $a$）则会生成 $120$ 个排列，会导致某些重复的排列被计算多次，从而使得答案增多。

因此本题要对字符串本身进行全排列，它的用法类似于对字符串直接排序。

即 next_permutation(s.begin(), s.end())。

注意使用之前需要先保证 $s$ 初始是字典序最小的情况，即调用 sort(s.begin(), s.end()) 先初始化为字典序最小的情况。

接下来即对于一个字符串 $s$，验证是否具有长度为 $k$ 得回文子串，可以用打标记得思想实现。

定义 bool check(l, r) 的函数用于判断字符串 $s$ 的区间 $$l\sim r$ 是否回文。
接下来就是枚举所有长度为 $k$ 的区间，由于区间长度固定且是子串，枚举左端点 $i$ 即可，即可同步计算出右端点。
若存在一个区间是回文的，则当前排列是不合法的，打上标记。
最后根据标记变量的值来判定这个字符串是否符合要求即可。

时间复杂度：$O(n!\times n^2)$

例题六：最少操作数¶

交换相邻两行或列可以类比做冒泡排序，因此行或列的交换实际就是在对行或列重新排列。

因此本题需要全排列所有的可能，一共 $n!\times m!$ 种（嵌套的关系）。

因此需要两个编号数组 $a$ 和 $b$ 分别记录行和列的编号，初始化分别为 $1\sim n$ 与 $1\sim m$。

如何计算交换次数？

对于给定的排列 $a$，它初始是 $1\sim n$，变化为其它排列后，只需要计算出这个排列的逆序对个数即可，逆序对个数就是它的交换次数。
- 逆序对：当满足 $ia_j$ 就称 $(i,j)$ 是一个逆序对。
- 因为冒泡排序本质就是消除逆序对的过程。
总交换次数就等于行的交换次数加上列的交换次数。注意是加不是乘。
时间复杂度为：$O(n!\times m!\times n^2\times m^2)$。

例题七：[ABC150C] Count Order¶

简单题，对排列 $1\sim n$ 进行全排列，同时设置一个变量记录目前到了第几个排列，然后分别检验当前排列是否分别等于 $p$ 或 $q$。

例题八：[ABC198D] Send More Money¶

题意：给你三个字符串 $a,b,c$，将每个字符看作是一个 $0\sim 9$ 之间的数字，可以得到新的三个数字 $N_1,N_2,N_3$。要求：

每个字符对应的数字唯一，即若字母 $a$ 看作是 1，其他字母则不能用 $1$。
新的三个数字无前导 $0$ 且都是正整数。
满足以上条件后给定一个构造方案。

首先可以统计三个字符串中一共出现多少个不同的字符，若不同的个数大于 $10$ 则无解。

接下来可以对每一个字符重新映射成一个数字，例如把 $a$ 看作 $1$，以此类推。注意这里出现的字母不一定是按照 $a,b,c$ 这样连续的，可能是将 $a,d,z$ 重新编号为 $1,2,3$。具体可以用 map 实现。

string a, b, c;
cin >> a >> b >> c;
string s = a + b + c; // 拼到一起
for (auto x : s) vis[x - 'a'] = 1;
int num = 0;
for (int i = 0; i < 26; i++) num += (vis[i] == 1);
if (num > 10)
{
    cout << "UNSOLVABLE";
    return 0;
}
map<char, int> id;
int cnt = 0;
for (int i = 0; i < 26; i++)
{
    if (vis[i]) id[i + 'a'] = ++cnt; // 每个字母重新给个数值
}

接下来枚举 $0\sim 9$ 的排列，来重新检验是否生成的数值符合要求。

for (int i = 0; i < 10; i++) x[i] = i;
do
{
    if (!x[id[a[0]]] || !x[id[b[0]]]) continue;
    long long suma = 0;
    for (auto v : a) suma = suma * 10 + (x[id[v]]);
    long long sumb = 0;
    for (auto v : b) sumb = sumb * 10 + (x[id[v]]);
    long long sumc = 0;
    for (auto v : c) sumc = sumc * 10 + (x[id[v]]);
    if (suma && sumb && suma + sumb == sumc)
    {
        cout << suma << "\n" << sumb << "\n" << sumc;
        return 0;
    }
} while (next_permutation(x, x + 10));
cout << "UNSOLVABLE";