置换和排列
置换和排列是各类问题中都很常见的概念。
本文讨论的不是排列数
本文讨论的主题是全排列，而不是排列组合中的排列数。排列数的相关内容应当参考 排列组合。
约定
本文中如果不加说明，总是讨论有限的集合。
定义
一个集合
「置换」与「排列」
在中文语境下，「置换」通常指改变元素顺序，而「排列」通常指将元素排成一列。当元素之间存在自然的顺序时，这两个概念是一回事：「排列」可以看作「置换」的结果；而相较于元素的自然顺序，「排列」中元素的顺序就指定了「置换」。因为本文使用「排列」一词时，总假定集合上存在自然顺序，故而本文中不会特意区分这两个概念。
当然，没有自然顺序的元素也可以进行「排列」。这种「排列」常常出现在组合计数问题中。这超出了本文讨论的范畴。
设集合
记号
置换讨论的是元素间的对应关系，而并不关心元素具体是什么。因而，当讨论大小为
表示方法
置换有多种表示方法。这里，以如下置换为例，讨论不同的置换表示方法。
双行记号
集合
它表示置换
比如说，前文的例子可以按照双行记号写作
当然，也可以写作
单行记号
很多时候，集合
这更像自然语言中排列的概念。所以，有时候排列会用来称呼这个有序组。
前文的例子利用单行记号可以写作
这种单行的记号，常用来比较不同排列的大小。
轮换表示
置换还有一种更为紧凑的表达方式，称为置换的轮换表示。它将置换表示为一系列不相交的轮换的乘积。下面描述将给定置换写成轮换表示的步骤。
给定一个置换
- 如果
中还有未曾写下的元素，就写下一个左括号，并写下任意一个这样的元素； - 当前一个写下的元素是
时， - 如果
已经在前面写下过，就写上右括号，并返回步骤 1； - 如果
还没有写下过，就写下 ，并继续步骤 2；
- 如果
- 直到
的所有元素都已经写下，结束。
每一对括号中，都是一个轮换。括号中的元素个数，称为对应轮换的长度。实践中，常常省略掉长度为一的轮换。
前文的例子利用轮换表示可以写作
恒等变换中所有的轮换长度都是一，常常记作
复合
置换的复合就是映射的复合。置换的复合也常常称作置换的乘法。
给定两个置换
那么，它们的乘积
简单来说就是先经过
因为置换
连续多个置换的乘积称作排列的幂，可以使用 快速幂 加速计算。
逆置换
因为置换是双射，所以置换总有相应的逆置换。
给定置换
它的逆置换就是
在轮换表示中，只要对每个轮换取逆，就能得到原来的置换的逆；而对每个轮换取逆，只要把元素的书写顺序倒过来就可以了。比如说，上文中的例子
给定
轮换
轮换（cycle）本身是特殊的置换。轮换的特性是，从轮换中的任何一点
置换的轮换表示可以看作将置换写成这些特殊置换（即轮换）的乘积，因而置换的轮换表示也可以看作是置换的 轮换分解（cycle decomposition）。对于每个置换，它分解成轮换乘积的方式在不计顺序后都是唯一的。轮换可以看作是构成置换的基本单元。
置换的轮换分解有着清晰的几何意义。如果将集合
不动点
对换
任何置换都可以写作一系列对换的乘积。这相当于说，任何顺序的排列都可以通过一系列交换两个元素的操作恢复成指定的正序排列。这正是基于交换的排序算法在做的事情。
更进一步，冒泡排序算法 的正确性其实说明，任何置换都可以写作一系列相邻对换的乘积。这里的 相邻对换（adjacent transposition）指的是只交换相邻元素的对换。
性质
在应用中，常常需要关注单个置换的性质。
奇偶性
将轮换分解成对换的方式并不是唯一的。比如，
但是，置换分解成一系列对换时，需要的对换的数目的奇偶性是固定的。一个置换的对换分解的数目的奇偶性也称作置换的 奇偶性（parity）。
能够分解成偶数个对换的乘积的置换叫做偶置换，能够分解成奇数个对换的乘积的置换叫做奇置换。当
符号
根据置换的奇偶性，还可以定义置换的 符号（sign），记作
置换的乘积的符号，等于它们的符号的乘积，即
也就是说，两个奇偶性相同的置换的复合是偶置换，两个奇偶性不同的置换的复合是奇置换。这一结论，从对换分解的角度看是显然的。
特别地，单次对换必然改变置换的奇偶性。这也正解释了为什么虽然分解成对换的方式不唯一，但是所需的对换的数目的奇偶性是确定的。
置换的符号出现在 行列式的 Leibniz 展开 中。
置换的阶
置换的 阶（order）是指满足如下条件的最小正整数
有限集合上，所有置换的阶都是有限的。这意味着，从起始顺序出发，只要重复按照固定模式打乱给定序列，在有限时间内，总可以将排列恢复原样。
置换的型
将
且这些系数满足
给定置换的型，不同的置换的数目为
分析
这是因为，给定任何
如果仅仅给定置换分解成的轮换个数
从置换的型，可以方便地确定置换的阶和奇偶性等性质。
因为
同样地，因为
的奇偶性。这里，
置换的型在 Pólya 计数 中有重要作用。
排列相关
如果集合
表示。注意不要同轮换混淆。
逆序数
在一个排列中，如果某一个较大的数排在某一个较小的数前面，就说这两个数构成一个 逆序（inversion）或反序。这里的比较是在自然顺序下进行的。
在一个排列里出现的逆序的总个数，叫做这个置换的 逆序数。排列的逆序数是它恢复成正序序列所需要做相邻对换的最少次数。因而，排列的逆序数的奇偶性和相应的置换的奇偶性一致。这可以作为置换的奇偶性的等价定义。
求解逆序数的算法，可以使用 归并排序 或 树状数组，时间复杂度均为
参考实现
#include <iostream>
#include <vector>
// Merge sort and count inversions.
long long merge_sort(std::vector<int>& nums, int b, int e) {
// Return 0 when length <= 1.
if (e - b <= 1) return 0;
long long res = 0;
int m = (b + e) / 2;
// Merge_sort two halves.
res += merge_sort(nums, b, m);
res += merge_sort(nums, m, e);
// Temporary vector to store sorted array.
std::vector<int> tmp(e - b);
int i = b, j = m, k = 0;
while (i < m && j < e) {
if (nums[j] < nums[i]) {
tmp[k] = nums[j++];
// In this case, all elements in [i,m) are larger than element j.
res += m - i;
} else {
tmp[k] = nums[i++];
}
++k;
}
// Deal with remaining elements.
for (; i < m; ++i, ++k) {
tmp[k] = nums[i];
}
for (; j < e; ++j, ++k) {
tmp[k] = nums[j];
}
// Copy back to original vector.
for (i = b, k = 0; i < e; ++i, ++k) {
nums[i] = tmp[k];
}
return res;
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int& num : nums) {
std::cin >> num;
}
std::cout << merge_sort(nums, 0, n);
return 0;
}
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
// A simple BIT implementation.
class BIT {
int n;
std::vector<int> su;
public:
BIT(int n) : n(n), su(n + 1) {}
// Add v to the x-th number.
void add(int x, int v) {
for (; x <= n; x += x & (-x)) {
su[x] += v;
}
}
// Get the cumulative sum till the x-th number.
int query(int x) {
int res = 0;
for (; x; x &= x - 1) {
res += su[x];
}
return res;
}
};
// Count inversions.
long long solve(const std::vector<int>& nums) {
// Discretization.
std::vector<int> sorted(nums);
std::sort(sorted.begin(), sorted.end());
sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
std::unordered_map<int, int> ids;
int m = sorted.size();
for (int i = 0; i < m; ++i) {
// Reverse the order.
// Now a smaller id means a larger element.
ids[sorted[i]] = m - i;
}
// Main part.
BIT bit(m);
long long res = 0;
for (int num : nums) {
int id = ids[num];
// Get inversion pair (i,j) with j the current element.
// Namely, count the number of elements larger than
// the current one but located before it.
res += bit.query(id - 1);
// Insert the current element to the BIT.
bit.add(id, 1);
}
return res;
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int& num : nums) {
std::cin >> num;
}
std::cout << solve(nums);
return 0;
}
顺序
排列之间是可以比较大小的。因为每个单行记号就是一个字符串，排列的顺序就是这个字符串上的 字典序。
在 C++ 的 STL 库 <algorithm> 中可以使用 prev_permutation 和 next_permutation 分别找到当前排列按照字典序的上一个和下一个排列。
排名
将
在中文竞赛圈，这个排名常称作排列的「康托展开」，但这种名称并不规范。更为严谨的说法是，一个排列的排名的康托展开，对应着该排列的 Lehmer 码（Lehmer code）。
关于「康托展开」
正如名字所暗示的那样，康托展开是指一种将自然数展开为数列的方法。它可以看作是一种特殊的进制，也叫做 阶乘进制（factorial number system）。这种进制中，不同的数位对应的底数（radix）并不相同。比如，十进制数
它表示如下含义
康托对于这类混合底数的进制进行了研究，故而自然数在这种进制下的数码表示也常称作自然数的康托展开。
示例
不熟悉排名的计算方法的读者，可以通过这个简单的例子理解下面的算法的基本思路。
要计算排列
- 第
位的选取要小于 ，只能取自 ，后面 位可以任意选取，共 个可选的排列； - 如果第
位也选择 ，那么第 位的选取要小于 ，只能取自 （这里， 已经选过了），后面的 位可以任意选取，共 个可选的排列； - 类似地，前
位的选取和 相同时，第 位的选取要小于 ，只能取自 ，后面的 位可以任意选取，共 个可选的排列； - 前
位的选取和 相同时，第 位的选取要小于 ，只能取自 ，后面的 位可以任意选取，共 个可选的排列； - 前
位的选取和 相同时，第 位的选取要小于 ，只能取自 ，后面的 位可以任意选取，共 个可选的排列； - 前
位的选取和 相同时，第 位的选择无法得到比 更小的排列，所以共 个可选的排列。
因此，排列
对于不同的排列，关键的点在于确定阶乘前面的系数。实际上，这些系数正是排在该位置之后却小于该位置元素的元素数目。
从例子中可以知道，求解给定排列的排名的算法，可以分为两步：
-
将给定的长度为
的排列转化为它的 Lehmer 码，即长度为 的序列 ，其中，第 位是 也就是在排列中，排在第
位后面，但是却比 小的元素个数。它等于尚未使用的元素中给定元素的排名（减一）。 -
将 Lehmar 码看作是自然数的康托展开，求出原来的自然数，并加一。也就是说，最终的排名等于
要求解这一问题的逆问题，即给定排名求解相应的排列，只要将上述过程反过来操作即可。在这一过程中求得的 Lehmer 码中的数字之和，就是排列的逆序数。
编程实现时，关键是要能够快速计算「尚未使用的元素中给定元素的排名」（求排名时）和「尚未使用的元素中给定排名的元素」（求排列时），这些都可以通过 树状数组 或 线段树 等数据结构维护。正反操作的时间复杂度均为
参考实现
#include <iostream>
#include <vector>
// A simple BIT implementation.
class BIT {
int n;
std::vector<int> su;
public:
BIT(int n) : n(n), su(n + 1) {}
// Add v to the x-th number.
void add(int x, int v) {
for (; x <= n; x += x & (-x)) {
su[x] += v;
}
}
// Get the cumulative sum till the x-th number.
int query(int x) {
int res = 0;
for (; x; x &= x - 1) {
res += su[x];
}
return res;
}
};
// Get the rank of a permutation of 1~n.
long long find_rank(const std::vector<int>& nums) {
int n = nums.size();
BIT bit(n);
long long fac = 1;
long long res = 0;
// Reverse iteration.
for (int i = n - 1; i >= 0; --i) {
// Count the number of elements smaller than the current one.
res += bit.query(nums[i] - 1) * fac;
// Insert the current element into the BIT.
bit.add(nums[i], 1);
// Update the factorial.
fac *= n - i;
}
return res + 1;
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int& num : nums) {
std::cin >> num;
}
std::cout << find_rank(nums);
return 0;
}
#include <cmath>
#include <iostream>
#include <vector>
// A simple BIT implementation.
class BIT {
int n;
std::vector<int> su;
public:
BIT(int n) : n(n), su(n + 1) {}
// Fill the BIT with one.
void fill() {
for (int x = 1; x <= n; ++x) {
su[x] += x & (-x);
}
}
// Add v to the x-th number.
void add(int x, int v) {
for (; x <= n; x += x & (-x)) {
su[x] += v;
}
}
// Get the k-th smallest element.
int find_kth(int k) {
int ps = 0, x = 0;
for (int i = log2(n); i >= 0; --i) {
x += 1 << i;
if (x >= n || ps + su[x] >= k) {
x -= 1 << i;
} else {
ps += su[x];
}
}
return x + 1;
}
};
// Find the k-th permutation of 1~n.
std::vector<int> find_permutation(int n, long long k) {
--k;
// Expand rank to Lehmer code.
std::vector<int> lehmer(n);
for (int i = 1; i <= n; ++i) {
lehmer[n - i] = k % i;
k /= i;
}
BIT bit(n);
// Set all values in BIT to one.
bit.fill();
std::vector<int> res(n);
for (int i = 0; i < n; ++i) {
// Find the lehmer[i]-th smallest unused element.
res[i] = bit.find_kth(lehmer[i] + 1);
// Remove it from the BIT.
bit.add(res[i], -1);
}
return res;
}
int main() {
int n;
long long k;
std::cin >> n >> k;
auto res = find_permutation(n, k);
for (int num : res) {
std::cout << num << ' ';
}
return 0;
}
参考资料与注释
创建日期: 2022年9月28日