本节书摘来自异步社区《趣题学算法》一书中的第1章1.5节置换与轮换，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。
1.5 置换与轮换
设有n个两两不等的元素a1, a2, …, an构成的集合A，考虑A到自身的一个1-1变换σ：a'1=σ(a1)， a'2=σ(a2)，…，a'n=σ(an)。换句话说，a'1，a'2，…，a'n是a1, a2, …, an的一个重排。数学中，称这样的对应关系σ为A的一个置换。
【例1】集合A={2，4，3，1}，σ(2)=1，σ(4)=2，σ(3)=3，σ(1)=4就是A上的一个置换。
设σ为A={a1, a2, …, an}的一个置换： a2=σ(a1)， a3=σ(a2)，…，an=σ(an−1)，则称σ为A上的一个轮换。
【例2】例1中，由于σ(2)=1，σ(1)=4，σ(4)=2，故σ可视为A的子集合A1={2，1，4}上的一个轮换σ1。
【例3】单元素集合A={a}上的恒等变换σ(a)=a视为轮换。
置换与轮换之间有如下的重要命题。
定理1-2
集合A={a1, a2, …, an}上的任何一个置换σ，均可唯一[5]地分解成A的若干个两两不相交的子集上的轮换，且这些子集的并即为A。
【例4】例1中A={2，4，3，1}上的置换σ可以分解成例2中A1上的σ1：2→1，1→4，4→2和A2={3}上的恒等变换σ2：3→3，且A= A1∪A2，A1∩A2=Ø。
定理1-2的证明如下。
对集合A所含的元素个数n做数学归纳。当n=1时，A上的任何变换就是恒等变换，所以本身就是一个轮换。对n>1，假定对元素个数k
问题描述
农夫John有N（1 leqslant Nleqslant 10 000）头牛妞，晚上她们要排成一排挤奶。每个牛妞拥有唯一的一个值介于1～100000的表示其暴脾气程度的指标。由于暴脾气的牛妞更容易损坏John的挤奶设备，所以John想把牛妞们按暴脾气指数的升序（从小到大）重排牛妞们。在此过程中，两个牛妞（不必相邻）的位置可能被交换，交换两头暴脾气指数为X、Y的牛妞的位置要花费X+Y个时间单位。
请你帮助John计算出重排牛妞所需的最短时间。
输入
输入文件中包含若干个测试案例数据。每个测试案例由两行数据组成：
第1行是一个表示牛妞个数的整数N。
第2行含N个用空格隔开的整数，表示每个牛妞的暴脾气指数。
N=0是输入数据结束的标志。对此案例无需做任何处理。
输出
对每一个测试案例输出一行包含一个表示按暴脾气指数升序重排牛妞所需的最少时间的整数。
输入样例
3
2 3 1
6
4 3 1 5 2 6
0
输出样例
7
18
解题思路
（1）数据的输入与输出
本问题输入文件包含若干个测试案例，每个案例的输入数据有两行：第1行含有1个表示牛妞个数的整数N，第2行含有N个表示诸牛妞脾气指数的整数。N=0为输入数据结束标志。可以将案例中牛妞脾气指数组织成一个数组，对此数组计算按脾气指数升序排列重排牛妞的最小代价。将计算所得结果作为1行写入输出文件。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取人数N
4 while N≠0
5 do 创建数组a[1..N]
6 for i←1 to N
7 do 从inputdata中读取a[i]
8 result←COW-SORTING(a)
9 将result作为一行写入outputdata
10 从inputdata中读取案例数据N
11 关闭inputdata
12 关闭outpudata
其中，第8行调用过程COW-SORTING(a)计算将牛妞们按脾气指数升序排序所花的最小代价，是解决一个案例的关键。
（2）处理一个案例的算法过程
对于一个案例，设置计数器count，初始化为0。设n个牛妞的脾气指数为a1, a2, …, an，按升序排列为a'1, a'2, …, a'n。这实际上就是集合A={a1, a2, …, an}上的一个置换σ。按定理1-2知，该置换可表示为A的m（1leqslantmleqslantn）个两两不相交子集A1，A2，…，Am（且xi _{i=1}^{m}{{A}_{i}}=A）上的轮换σ1，σ2，…，σm。利用定理1-2的证明中的构造方法，依次分解出每个子集Ai={ai1, ai2, …, aik}（1leqslantileqslantm），若Ai是单元素集合，则定义在其上的轮换就是恒等变换，不发生任何代价。今设k>0，直接完成轮换即ai1→ai2→…→aik→ai1。每个元素都参加2次交换，故代价为sumnolimits_{t=1}^{k}{2{{a}_{{{i}_{t}}}}}。设{ai1, ai2, …, aik}中的最小者为ti，利用该元素做如下的对换：将ti与应该在其位置上元素交换。这样，除了ti本身，每个元素都按这样的方式做了一次交换，从而到达了合适的位置，而ti做了k−1次交换，故代价为sumnolimits_{t=1}^{k}{2{{a}_{{{i}_{t}}}}}+(k-2){{t}_{i}}。这显然比sumnolimits_{t=1}^{k}{2{{a}_{{{i}_{t}}}}}优越，但是有一种情况也许比这更好：将A={a1, a2, …, an}中的最小值元素amin先与上述{ai1, ai2, …, aik}中的最小元素ti交换，产生代价amin+ti。然后按上述方式进行操作，产生代价sumnolimits_{t=1}^{k}{{{a}_{{{i}_{t}}}}}+(k-1){{a}_{min }}。最后再amin将与ti交换，产生代价amin+ti。将三者相加得到此方式的总代价：sumnolimits_{t=1}^{k}{{{a}_{{{i}_{t}}}}}+(k+1){{a}_{min }}+{{t}_{i}}。这样，我们只需选取min{sumnolimits_{t=1}^{k}{2{{a}_{{{i}_{t}}}}}+(k-2){{t}_{i}}，sumnolimits_{t=1}^{k}2{{{a}_{{{i}_{t}}}}}+(k+1){{a}_{min }}+{{t}_{i}}}即为完成子集{ai1, ai2, …, aik}对换的最小代价。按此方法将每个子集对换的最小代价累加到计数器count中，即为案例所求。将算法思想表达为伪代码过程如下。
COW-SORTING(a)
1 n←length[a], count←0
2 copy a to b
3 SORT(b)
4 amin←b[1]
5 while n>0
6 do j←a中首个非0元素下标
7 ti←∞, sum←a[j]
8 k←1, ai←a[j]
9 a[j]←0, n←n-1
10 while b[j]≠ai
11 do k←k+1
12 sum←sum+b[j]
13 if ti>b[j]
14 then ti←b[j]
15 j←FIND(a, b[j])
16 a[j]←0, n←n-1
17 if k>1
18 then count←count+sum+min{(k-2)*ti, (k+1)*amin}
19 return count
算法1-12 计算将牛妞们按脾气指数升序重排的最小代价的算法过程
算法中设置b为数组a按升序排序的结果（第2～3行）。a、b元素之间的对应关系是根据对应下标确定的，即a[i] underrightarrow{sigma } b[i]（1leqslantileqslantn）。第5～18行的while循环每次重复构造A的一个轮换子集，并计算完成该子集元素交换的最小代价，累加到计数器count（第1行初始化为0）中。具体地说，第6行取a中未曾访问过的元素（a中访问过的元素置为0）下标为j，设新的子集上轮换的首元素ai。第10～15行的while循环按条件b[j]≠ai重复，构造一个轮换子集。一旦该条件为假（b[j]=ai）意味着轮换完成。在构造过程中，第11行子集元素个数k自增1，第12行将新发现的元素添加到和sum（第7行初始化为该子集的首元素ai）中，第13～14行跟踪该子集的最小元素ti（第7行初始化为∞）。第15行找出下一个对应元素下标j，第16行将已经完成访问的a[j]置为0，且将尚未访问过的元素个数n（第1行初始化为a的元素个数）自减1。一旦完成一个轮换子集的构造（第10～16行的while循环结束），第17～18行根据子集元素个数k是否大于1，按此前讨论的公式决定count的增加值。
算法的运行时间取决于第11～16行操作被重复的次数。由于每次重复a中的一个元素值被值为0，而外层循环条件为a中非0元素个数n>0，所以第11～16行的操作一定被重复a的元素个数次N（即牛妞的个数）。在11～16行的各条操作中，第15行调用FIND过程在a中查找值为b[j]的元素下标，这将花费O(N)时间，所以整个算法的运行时间是O(N2)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Cow Sorting中，读者可打开文件CowSorting.cpp研读，并试运行之。C++代码的解析请阅读第9章9.4.2节中程序9-53的说明。
计数问题是最基本、最常见的计算问题。本章通过解决10个计算问题讨论了解决计数问题的几个常用的算法设计方法，包括累积法（问题1-1、问题1-2、问题1-3和问题1-4）、数学计算法（问题1-5、问题1-6和问题1-7）、加法原理和乘法原理（问题1-8）、图的性质（问题1-9）和置换与轮换（问题1-10）。
[1] 见本书0.5节。
[2] 见本书0.6节。
[3] 参阅本书第7章节7.3。
[4]
[5] 此处的唯一性指的是将轮换作为元素构成的集合是唯一的。
本文仅用于学习和交流目的，不代表异步社区观点。非商业转载请注明作译者、出处，并保留本文的原始链接。
