aiwiki.page
中文
数学 / 代数与数论 / permutation

置换

置换是集合到自身的双射,是计数、对称性、代数、算法和概率论中的基本概念。

42 个关键词36 个词条链接到这里5 个尚未撰写AI 撰写
双射函数组合数学函数(数学)阶乘单射函数二项式系数函数复合反函数置换

置换是对互不相同的对象进行重新排列;更形式化地说,它是一个集合到自身的双射函数。对于有限集,只要先为其元素指定一个初始顺序,这两种描述就是等价的:每个元素的像确定了它在新排列中的位置,而每个元素在新排列中都恰好出现一次。无限集上也存在置换,此时,双射的表述比重新排列有限列表的直观图景更为一般。

置换将组合数学中的计数与对称性的代数研究联系起来。它们可以描述对象的各种可能次序、图中顶点的重新标号、多项式根之间的互换,以及计算过程中各项的位置变动。将置换分解为循环,可以揭示其内部结构;将置换区分为偶置换和奇置换,可以确定行列式中各项的符号;而置换在复合运算下构成的对称群,则在现代代数中占据核心地位。用于生成、排序和抽样置换的算法,使这些数学结构能够直接应用于计算和统计。

定义与初等计数

对于集合 XX,置换是一个既是单射又是满射的函数 σ:X→X\sigma:X\to X。每个元素都恰有一个像,而每个元素又恰好是一个元素的像。因此,置换既不会丢弃对象,也不会重复对象。如果 X={1,…,n}X=\{1,\ldots,n\},那么像 3,1,4,23,1,4,2 这样的排列就表示满足 σ(1)=3\sigma(1)=3、σ(2)=1\sigma(2)=1、σ(3)=4\sigma(3)=4 和 σ(4)=2\sigma(4)=2 的置换。XX 上所有置换构成的集合通常记作 Sym⁡(X)\operatorname{Sym}(X);对于上述标准的 nn 元集合,通常记作 SnS_n。

置换的第一项有 nn 种选择,第二项有 n−1n-1 种选择,此后可选的数目依次减少,直到最后一项只有一种选择。因此,

∣Sn∣=n!=n(n−1)⋯2⋅1.|S_n|=n!=n(n-1)\cdots2\cdot1.

阶乘的约定 0!=10!=1 有一个直接的解释:空集到自身恰好有一个双射,即空函数。置换的数量增长很快。五个对象有 5!=1205!=120 个置换,十个对象有 10!=3,628,80010!=3{,}628{,}800 个置换,而二十个对象则有 20!=2,432,902,008,176,640,00020!=2{,}432{,}902{,}008{,}176{,}640{,}000 个置换。这种增长极大地限制了对各种排列进行穷举搜索的可行性。

在初等计数中,“排列”有时采用更宽泛的含义,指从 nn 个不同对象中不放回地选取 kk 个对象,并按顺序排好。这样的排列数为

P(n,k)=n!(n−k)!.P(n,k)=\frac{n!}{(n-k)!}.

严格来说,这样的选取是从一个含 kk 个元素的位置集合到一个含 nn 个元素的对象集合的单射函数,未必是整个对象集合上的置换。若选取时不考虑顺序,则有 (nk)\binom nk 种可能,其中二项式系数消除了所选对象的 k!k! 种不同次序所造成的重复计数。

存在重复符号时,还需要作进一步区分。如果 nn 个位置上放置的各类符号分别出现 m1,…,mrm_1,\ldots,m_r 次,其中 ∑imi=n\sum_i m_i=n,那么可区分的排列数为

n!m1!⋯mr!.\frac{n!}{m_1!\cdots m_r!}.

例如,BANANA 中的字母可以排成 6!/(3!2!)=606!/(3!2!)=60 个不同的字符串。如果给这六个字母分别加上独立标签,再进行置换,仍会得到 6!6! 个置换;但交换无法区分的相同字母,并不会改变显示出来的字符串。因此,计数结果取决于究竟是区分对象本身,还是仅区分其外观所呈现的类别。

记法、复合与逆置换

双行记法将置换的定义域元素写在上行,将对应的像写在下行:

σ=(1234531542).\sigma= \begin{pmatrix} 1&2&3&4&5\\ 3&1&5&4&2 \end{pmatrix}.

当默认上行为 1,2,…,n1,2,\ldots,n 时,单行记法只记录下行,在这里就是 3154231542。当标号包含多位数字时,需要使用分隔符。单行记法特别适合研究递增子序列等次序性质,而循环记法则突出函数的反复作用。

置换通过函数复合进行组合。按照标准约定

(στ)(x)=σ(τ(x)),(\sigma\tau)(x)=\sigma(\tau(x)),

最右边的置换先作用。例如,若 σ=(1 2)\sigma=(1\,2) 交换 1 和 2,τ=(2 3)\tau=(2\,3) 交换 2 和 3,则 στ=(1 2 3)\sigma\tau=(1\,2\,3),而 τσ=(1 3 2)\tau\sigma=(1\,3\,2)。这两个乘积不同,说明置换的复合一般不满足交换律。有些文献采用从右侧作用的置换,并按相反的顺序解读乘积,因此在比较计算结果时,必须明确所用的约定。

恒等置换 ee 对每个元素都满足 e(x)=xe(x)=x。每个置换都有一个反函数,称为逆置换,记作 σ−1\sigma^{-1},由下式确定:

σ−1(σ(x))=x.\sigma^{-1}(\sigma(x))=x.

在双行记法中,先交换两行,再重新排列各列,使上行恢复标准顺序,就得到逆置换。上述例子的逆置换用单行记法表示为 2514325143。求逆会颠倒乘法的顺序:

(στ)−1=τ−1σ−1.(\sigma\tau)^{-1}=\tau^{-1}\sigma^{-1}.

整数次幂表示反复复合,其中 σ0=e\sigma^0=e,负整数次幂则通过逆置换来定义。

另一项约定涉及重排位置与重新标记数值之间的区别。如果将列表视为函数 a:{1,…,n}→Aa:\{1,\ldots,n\}\to A,那么规则

(σ⋅a)i=aσ−1(i)(\sigma\cdot a)_i=a_{\sigma^{-1}(i)}

会将原来位于位置 jj 的元素移到位置 σ(j)\sigma(j)。公式中的逆置换保证了先作用 τ\tau、再作用 σ\sigma,与作用 στ\sigma\tau 一致。相比之下,表达式 aσ(i)a_{\sigma(i)} 指定的是每个新位置应读取哪个原有元素。这两种约定都很有用,但它们描述的索引重排方向相反。在数组编程、坐标变换以及涉及带索引求和的公式中,这一区别十分重要。

循环分解与阶

从有限集合的一个元素 aa 出发,反复施加同一个置换,得到

a,σ(a),σ2(a),….a,\sigma(a),\sigma^2(a),\ldots.

由于集合有限,最终必有元素重复出现。双射性保证了第一次重复出现的元素就是 aa,而不会从外部进入某个循环。由此得到的轨道称为循环,记作 (a1 a2 … ak)(a_1\,a_2\,\ldots\,a_k),表示 aia_i 映到 ai+1a_{i+1},而 aka_k 映回 a1a_1。只含一个元素的循环就是一个不动点。

每个有限置换都能分解为若干互不相交的循环。例如,

(12345673125467)=(1 3 2)(4 5)(6)(7).\begin{pmatrix} 1&2&3&4&5&6&7\\ 3&1&2&5&4&6&7 \end{pmatrix} =(1\,3\,2)(4\,5)(6)(7).

互不相交的循环作用于不同的元素,因此彼此可交换。所以,它们在表达式中的排列顺序无关紧要;循环内部各项的循环移位也不会改变该循环:(1 3 2)=(3 2 1)(1\,3\,2)=(3\,2\,1)。除这些表示方式上的自由外,分解是唯一的。不动点通常省略不写,因此,如果需要知道不动点的个数,就必须明确置换所作用的集合。

各循环的长度决定了置换的阶,也就是使 σm=e\sigma^m=e 成立的最小正整数 mm。每个循环在作用次数为其长度的倍数时都会恢复初始状态,因此置换的阶就是所有循环长度的最小公倍数。上例中置换的阶为 lcm⁡(3,2,1,1)=6\operatorname{lcm}(3,2,1,1)=6。更一般地,一个 kk 元循环的 rr 次幂会分解成 gcd⁡(k,r)\gcd(k,r) 个循环,每个循环的长度为 k/gcd⁡(k,r)k/\gcd(k,r)。因此,一个六元循环的平方是两个三元循环的乘积,而它的立方则是三个对换的乘积。

对合是指平方为恒等置换的置换。它的循环长度只能是 1 或 2,因此,无不动点的对合等价于将所作用集合中的元素两两配对。对于 2m2m 个带标号的元素,这样的配对方式共有

(2m)!2mm!.\frac{(2m)!}{2^m m!}.

分母消除了每一对中两个元素的排列顺序,以及各对之间排列顺序造成的重复计数。

对于无限集合,仅靠有限循环未必能完成分解。双射作用下的非周期轨道以全体整数为索引,而不只是以非负整数为索引。例如,Z\mathbb Z 上的平移 k↦k+1k\mapsto k+1 就构成一个无限轨道。每个置换都将其定义域划分为有限循环和这样的双向无限轨道。与有限置换不同,无限置换的阶不一定有限。

对换、逆序与奇偶性

对换交换两个元素,并保持其余所有元素不变。对换可以生成所有有限排列,因为一个轮换可以写成

(a1 a2 … ak)=(a1 ak)(a1 ak−1)⋯(a1 a2).(a_1\,a_2\,\ldots\,a_k) =(a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2).

因此,一个 kk-轮换在这一表达式中需要 k−1k-1 个对换。更一般地,若一个 nn 个元素的排列包含 cc 个轮换(包括不动点),则将其表示为任意对换之积所需的最少对换数为 n−cn-c。每次对换都会将两个轮换合并为一个,或将一个轮换拆分为两个,由此便可得到相应的下界。

虽然对换分解并不唯一,但分解长度的奇偶性保持不变。若一个排列可以表示为偶数个对换之积,就称其为偶排列;否则称为奇排列。排列的符号满足

sgn⁡(σ)∈{1,−1},sgn⁡(στ)=sgn⁡(σ)sgn⁡(τ).\operatorname{sgn}(\sigma)\in\{1,-1\}, \qquad \operatorname{sgn}(\sigma\tau) =\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau).

对于含有 cc 个轮换的排列,

sgn⁡(σ)=(−1)n−c.\operatorname{sgn}(\sigma)=(-1)^{n-c}.

特别地,一个 kk-轮换的符号为 (−1)k−1(-1)^{k-1}。当 n≥2n\ge2 时,乘以任意一个固定的对换,就能将每个偶排列与一个奇排列配对,因此在 n!n! 个排列中,奇排列和偶排列各占一半。

奇偶性也可以从元素的次序关系来描述。对于用单行记法表示的排列,若一对下标 i<ji<j 满足 σ(i)>σ(j)\sigma(i)>\sigma(j),则称其为一个逆序。用 inv⁡(σ)\operatorname{inv}(\sigma) 表示逆序的个数,则有

sgn⁡(σ)=(−1)inv⁡(σ).\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}.

例如,31423142 的逆序为 (1,2)(1,2)、(1,4)(1,4) 和 (3,4)(3,4),因此它是奇排列。交换相邻两项会使逆序数恰好增加或减少一,这直接解释了逆序数与对换分解奇偶性之间的关系。

相邻对换 si=(i  i+1)s_i=(i\,\,i+1) 可以生成 SnS_n,但它们与任意对换所对应的距离概念不同。将一个排列排成有序序列所需的最少相邻交换次数,恰好等于它的逆序数。因此,当允许交换任意两个位置时,n−cn-c 衡量的是最小排序代价;而当只允许交换相邻位置时,衡量最小排序代价的则是 inv⁡(σ)\operatorname{inv}(\sigma)。这两种度量自然地出现在排序算法和排名列表的比较中。

对称群、群作用与共轭

在复合运算下,一个集合上的所有置换构成一个群:复合运算满足结合律,存在单位元,且每个元素都有逆元。对于含 nn 个元素的集合,这个群就是对称群 SnS_n,其阶为 n!n!。对称群的任意子群都称为置换群。这样的子群可以表示保持某种特定结构不变的重排,而不必包含所有可能的重排。例如,正方形的旋转和反射在其四个顶点上诱导出八个置换,只占 S4S_4 的 24 个元素中的一小部分。

群在集合 XX 上的群作用,是指为每个群元素指定一个 XX 上的置换,且这种对应保持乘法运算。等价地,它是一个到 Sym⁡(X)\operatorname{Sym}(X) 的同态。如果不同的群元素诱导出不同的置换,就称这个作用是忠实的。凯莱定理指出,每个群都有忠实的置换表示:群 GG 通过左乘作用于自身的元素,即 x↦gxx\mapsto gx。当 GG 为有限群时,这就将它嵌入了 S∣G∣S_{|G|},不过也可能存在作用于更小集合的忠实作用。

对置换进行共轭相当于重新标记元素:

τ(a1 … ak)τ−1=(τ(a1) … τ(ak)).\tau(a_1\,\ldots\,a_k)\tau^{-1} =(\tau(a_1)\,\ldots\,\tau(a_k)).

共轭保持循环长度不变。反过来,SnS_n 中的两个元素共轭,当且仅当它们的循环长度多重集相同。这些多重集对应于 nn 的整数分拆。如果某种循环类型中长度为 ii 的循环有 mim_i 个,且满足 ∑iimi=n\sum_i i m_i=n,那么具有这种循环类型的置换数为

n!∏iimimi!.\frac{n!}{\prod_i i^{m_i}m_i!}.

其中,因子 imii^{m_i} 用于消除各循环内部循环移位造成的重复计数,mi!m_i! 则用于消除等长循环之间交换次序造成的重复计数。

所有偶置换构成交错群 AnA_n。当 n≥2n\ge2 时,它是 SnS_n 中指数为二的正规子群,因为它是符号同态的核。当 n≥5n\ge5 时,AnA_n 是单群:除了自身和单位子群之外,它没有其他正规子群。这一结构性质有助于解释置换在伽罗瓦理论中的重要意义。特别地,n≥5n\ge5 时 SnS_n 的不可解性,是五次及以上多项式方程不存在一般根式求解公式的根本原因。

置换矩阵与线性代数

置换可以用作用于坐标向量的矩阵来表示。采用约定

Pσej=eσ(j),P_\sigma e_j=e_{\sigma(j)},

其中 e1,…,ene_1,\ldots,e_n 为标准基向量,由此定义置换矩阵 PσP_\sigma。该矩阵的第 σ(j)\sigma(j) 行、第 jj 列元素为 1,其余位置均为零。每行和每列都恰有一个 1。在这一约定下,

PσPτ=Pστ,(Pσx)i=xσ−1(i).P_\sigma P_\tau=P_{\sigma\tau}, \qquad (P_\sigma x)_i=x_{\sigma^{-1}(i)}.

这样就把置换实现为坐标向量空间上的可逆线性映射。

置换矩阵是正交矩阵,因为坐标的置换保持通常的内积不变。因此,

Pσ−1=PσT=Pσ−1.P_\sigma^{-1}=P_\sigma^{\mathsf T}=P_{\sigma^{-1}}.

其行列式等于 sgn⁡(σ)\operatorname{sgn}(\sigma),而矩阵的迹等于不动点的个数。对基作适当重排后,矩阵可分解为与各个不相交循环对应的分块。一个长度为 kk 的循环所对应分块的特征多项式为 tk−1t^k-1,其复特征值为所有 kk 次单位根。这些性质将循环结构转化为谱信息。

置换也用于索引任意 n×nn\times n 矩阵的行列式展开式:

det⁡A=∑σ∈Snsgn⁡(σ)∏i=1nai,σ(i).\det A= \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^{n}a_{i,\sigma(i)}.

每一项都从每行和每列中各选取一个元素。略去符号因子便得到积和式;它在形式上与行列式相似,计算性质却截然不同。若一个仅由零和一组成的矩阵描述两个各含 nn 个元素的集合之间允许的配对关系,则其积和式给出仅使用允许配对的双射数量。

在数值计算中,左乘置换矩阵会重排行,右乘则按照所采用的约定重排列。行置换在高斯消元法的选主元过程中起着关键作用:改变方程的顺序有助于避开不合适的主元。同时置换行和列可以使分块结构显现出来,或改善稀疏计算的组织方式,而所得矩阵仍表示原有线性变换,只是所用的基发生了变化。

置换矩阵还将离散排列与凸优化联系起来。双随机矩阵的所有元素均非负,且每行、每列的元素之和都等于 1。伯克霍夫–冯·诺伊曼定理指出,每个这样的矩阵都是置换矩阵的凸组合。因此,这些离散的置换矩阵恰好构成双随机矩阵多胞体的全部极点;这一结果是指派问题及其线性规划表述的基础。

受限排列与枚举结构

许多计数问题涉及满足附加条件的排列。**错排**是不含不动点的排列。若以 DnD_n 表示错排的数量,则由容斥原理可得

Dn=n!∑k=0n(−1)kk!.D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

求和中的各项交替减去和加回那些使指定位置子集保持不动的排列。因此,D4=9D_4=9,且 Dn/n!D_n/n! 趋于 e−1e^{-1}。错排可用于描述无人拿到自己物品的分配问题;不过,如果还要限制哪些人可以拿到哪些物品,就需要更一般的方法。

按循环个数计数会得到无符号第一类斯特林数,通常记为 c(n,k)c(n,k):它表示 nn 个元素的排列中恰有 kk 个循环的排列数。这些数满足递推关系

c(n,k)=c(n−1,k−1)+(n−1)c(n−1,k).c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k).

新增的元素要么自成一个循环,要么插入已有循环中某个元素之后,而这样的已有元素共有 n−1n-1 个。其生成恒等式为

x(x+1)⋯(x+n−1)=∑k=0nc(n,k)xk.x(x+1)\cdots(x+n-1)=\sum_{k=0}^{n}c(n,k)x^k.

这个公式用一个多项式记录了循环个数的完整分布。

另一些统计量取决于位置的线性顺序,而非循环结构。若位置 i<ni<n 满足 σ(i)>σ(i+1)\sigma(i)>\sigma(i+1),就称该位置为一个下降。欧拉数 A(n,k)A(n,k) 表示恰有 kk 个下降的排列数。逆序数则有另一种生成多项式:

∑σ∈Snqinv⁡(σ)=∏j=1n(1+q+⋯+qj−1).\sum_{\sigma\in S_n}q^{\operatorname{inv}(\sigma)} =\prod_{j=1}^{n}(1+q+\cdots+q^{j-1}).

将最大元素 nn 插入一个长度为 n−1n-1 的排列,即可得到这一结果:插入所产生的新逆序数可以是从 0 到 n−1n-1 的任意整数。这样的生成函数把组合构造转化为代数恒等式。

如果一个排列的某个子序列与 π\pi 具有相同的相对次序,就称该排列包含模式 π\pi。例如,元素 5,2,45,2,4 构成一个 312 模式,因为它们的相对大小依次为最大、最小、居中。模式规避限制的是这些相对次序结构,而不指定元素的实际数值。对于任意一个指定的长度为三的模式,规避该模式的排列数均由卡塔兰数给出:

Cn=1n+1(2nn).C_n=\frac{1}{n+1}\binom{2n}{n}.

栈排序是一个经典的算法实例:能够通过单个栈排成递增顺序的排列,恰好就是规避 231 模式的排列。这将受限排列与树、括号表达式以及递归分解联系起来。

生成、排名与排序算法

枚举所有置换时,每个置换都至少需要一次输出操作,因此,只要需要输出全部置换,就无法避免阶乘级的增长。不过,各种生成方法在输出顺序、内存占用以及相邻两次输出之间的变化幅度上,都有显著差异。字典序通过序列中第一个不同的位置来比较大小。为了得到下一个置换,算法先找到最靠右的上升相邻对,将其中的第一个元素与其右侧比它大的最小元素交换,再将该位置之后的后缀逆序。这一过程只需常数辅助空间,每一步的时间至多为线性。

最小变化算法则让相邻两次输出仅相差一个小操作。Steinhaus–Johnson–Trotter 算法通过相邻对换生成置换。它为各元素指定移动方向,每次移动能够越过相邻较小元素的最大元素,并在移动后反转所有比该元素大的元素的方向。Heap 算法是另一种经典的生成算法,相邻两次输出之间只进行一次交换。如果与排列相关的某个量在一次交换后可以低成本更新,而不必从头计算,这类方法就很有用。

置换也可以编码为整数。它的 莱默码的各位数字为

ci=#{j>i:σ(j)<σ(i)},0≤ci≤n−i.c_i=\#\{j>i:\sigma(j)<\sigma(i)\}, \qquad 0\le c_i\le n-i.

这些数字记录了每个元素后面有多少个比它小、且尚未使用的值。从零开始计数的字典序排名为

rank⁡(σ)=∑i=1nci(n−i)!.\operatorname{rank}(\sigma) =\sum_{i=1}^{n}c_i(n-i)!.

这种阶乘数制在 SnS_n 与从 0 到 n!−1n!-1 的整数之间建立了双射。由排名还原置换则是这一过程的逆过程:从尚未使用的标号所组成的有序列表中,依次选取元素。借助平衡数据结构,排名计算及其逆运算都可以在 O(nlog⁡n)O(n\log n) 时间内完成。

均匀随机生成可以通过 Fisher–Yates 洗牌算法实现。对于 i=n,n−1,…,2i=n,n-1,\ldots,2,算法从 1,…,i1,\ldots,i 中均匀随机选取一个整数 jj,并交换位置 ii 和 jj 上的元素。共有 n(n−1)⋯2=n!n(n-1)\cdots2=n! 个等概率的选择序列,每个序列都会产生一个不同的置换。因此,只要随机下标的选取无偏,这一算法就能在线性时间内进行均匀采样。

排序则从相反的角度看待问题:输入顺序确定了一个置换,排序就是将其化为恒等置换。对于键值互不相同的输入,基于比较的排序算法在最坏情况下至少需要 ⌈log⁡2(n!)⌉\lceil\log_2(n!)\rceil 次比较,因为二叉决策树必须区分 n!n! 种可能的输入顺序。由此便得到了熟知的 Ω(nlog⁡n)\Omega(n\log n) 下界。不过,利用基于归并的方法,可以在 O(nlog⁡n)O(n\log n) 时间内计算逆序数,而无须实际执行逆序数所对应的每一次相邻交换。

随机置换与统计推断

均匀随机置换为 SnS_n 中的每个元素赋予概率 1/n!1/n!。它的各个坐标都服从均匀分布:对于任意固定位置 ii,σ(i)\sigma(i) 取任何一个标号的可能性都相同。不过,这些坐标并不独立,因为不同位置不能取相同的值。这个简单的例子说明,边缘分布均匀并不意味着具有统计独立性,也使置换成为不放回抽样的基本模型。

设 FnF_n 为不动点的个数。对于每个位置,表示该位置是否为不动点的指示变量的期望值为 1/n1/n,因此由期望值的线性性质可得

E[Fn]=1.\mathbb E[F_n]=1.

当 n≥2n\ge2 时,其方差也为 1。随着 nn 增大,FnF_n 依分布收敛于均值为 1 的泊松分布。更一般地,若 CkC_k 为长度为 kk 的循环的个数,则

E[Ck]=1k(k≤n).\mathbb E[C_k]=\frac1k \qquad (k\le n).

因此,循环总数的期望值为调和数

Hn=∑k=1n1k.H_n=\sum_{k=1}^{n}\frac1k.

对于任意一组固定的长度,相应的循环个数渐近服从相互独立的泊松分布,均值分别为 1/k1/k。

置换中与次序有关的统计量呈现出不同的尺度。若 InI_n 为逆序数,则

E[In]=n(n−1)4,Var⁡(In)=n(n−1)(2n+5)72.\mathbb E[I_n]=\frac{n(n-1)}4, \qquad \operatorname{Var}(I_n)=\frac{n(n-1)(2n+5)}{72}.

任意两个位置上的值按递增或递减顺序排列的可能性相同,由此可得上述期望值。计算方差则需要考虑共享同一位置的比较之间的相依性。经过中心化和尺度标准化后,逆序数趋于服从正态分布。最长递增子序列具有不同的渐近行为:其长度的期望值渐近等于 2n2\sqrt n。

置换还为统计假设检验提供参照分布。置换检验对零假设模型或实验设计所允许的各种标号重排重新计算检验统计量。例如,在组容量固定的两组随机化实验中,相关重排对应于随机化方案所允许的处理分配方式。如果在指定的零假设下,所有允许的分配方式都等可能,那么通过枚举即可得到精确的随机化分布。

这种方法的依据并不只是标号可以机械地重新排列,而是零假设下的可交换性,或已知的分配机制。对于配对观测、区组、整群数据以及存在序列相依性的情形,可能需要采用受限置换,而不能任意打乱顺序。当完全枚举不可行时,可以随机抽取允许的重排方式,以近似参照分布。这一方法的有效性取决于允许采用的变换群以及所检验的假设。

历史发展与更广泛的应用

对排列进行系统计数的研究,早于将置换定义为双射的现代观点。在17世纪的欧洲,布莱兹·帕斯卡、皮埃尔·德·费马和戈特弗里德·威廉·莱布尼茨在组合数学方面的工作,推动了排列与组合成为数学研究的课题。莱布尼茨的《组合术论》于1666年问世。这些早期研究侧重于计数和符号组合,而非置换的抽象代数理论。

置换在代数中的作用,是随着方程研究的发展而逐渐确立的。在1770至1771年发表的研究中,约瑟夫-路易·拉格朗日考察了多项式的根发生置换时,由这些根构成的表达式如何变化。随后,保罗·鲁菲尼和尼尔斯·亨里克·阿贝尔为证明一般五次方程无法用根式求解作出了贡献。埃瓦里斯特·伽罗瓦在1830至1832年前后的研究中,将方程的可解性与保持代数关系不变的根的置换群联系起来。奥古斯丁-路易·柯西在置换群方面取得了重要成果,而阿瑟·凯莱于1854年的工作则推动了群概念的独立表述,使其不再依赖于某种具体的置换实现。

在图论中,顶点的置换相当于对图的顶点重新标号。如果这种置换保持邻接关系不变,它就是一个自同构。若一个图的邻接矩阵为 AA,且顶点 ii 被重新标记为 σ(i)\sigma(i),则新的邻接矩阵为

PσAPσ−1.P_\sigma A P_\sigma^{-1}.

图同构问题考察的是两个图能否通过这样的重新标号相互转化。置换也可用于表示路径规划问题的候选解:在旅行商问题中,城市的一种排序描述了一条巡回路线,不过,循环移位和逆序可能使多个排序表示同一条巡回路线。

实物益智玩具提供了具体的置换群实例。在滑块拼图中,合法移动会使涉及滑块顺序和空格位置的某些量保持不变,因此,并非所有看似可能的排列都能达到。魔方类益智玩具同样对各块的置换和朝向施加限制。这些例子区分了由所有设想中的重排构成的全对称群,以及由实际允许的移动所生成的子群。对它们的分析需要运用生成元、不变量和复合运算,而不只是计算排列的数量。

在密码学中,固定密钥下的分组密码相当于定长比特串集合上的一个置换:解密要求每个密文分组都有唯一对应的明文分组。现代安全要求关注这些由密钥确定的置换在计算上的表现,而不仅仅是它们是否为双射。在机器学习和科学计算中,置换对称性关注的则是索引的任意性。置换不变函数在输入重新排序后仍给出相同的输出,而置换等变函数的输出则会随之发生相应的重排。在表示集合、图、粒子或其他标签本身不具有内在含义的系统时,这些性质至关重要。