TAOCP 5,1.1 Exercise 12

Continuing the notation of the previous exercise, prove that if \(\pi_1\) and \(\pi_2\) are permutations and if E is the smallest transitive set containing \(E(\pi_1)\cup E(\pi_2)\) then \(\bar{E}\) is transitive.

反证：假设存在\((a,b) \in \bar{E}, (b,c) \in \bar{E}\)但\((a,c) \in E\)，显然\((a,b) \notin E(\pi_1)\)，\((b,c) \notin E(\pi_1)\)  ,所以\(c < b < a\)并且在\(\pi_1\)中保持顺序。同理此三个数在\(\pi_2\)中也保持顺序。

现在考察(a,c)，如果E中去除(a,c)传递性仍然成立，则与E为满足传递性的最小集合矛盾，所以E中必有元素(a,t)和(t,c)。(a,t)和(t,c)必然分别来自\(\pi_1\)和\(\pi_2\)，不失一般性，设
\(\pi_1=\ldots c \ldots b \ldots a \ldots t \ldots \)
\(\pi_2=\ldots t \ldots c \ldots b \ldots a \ldots \)

现在有两种情况
1） b>t, 则有 \((b,t) \in E(\pi_1), (t,c) \in E(\pi_2)\) 导致\((b,c) \in  E\) 与假设\((b,c) \in \bar{E}\)矛盾。
2） b<t 则有 \((a,t) \in E(\pi_1), (t,b) \in E(\pi_2)\) 导致\((a,b) \in E\) 与假设\((a,b) \in \bar{E}\)矛盾。

所以\((a,c) \in E\)不成立，\((a,c) \in \bar{E}\)，即\(\bar{E}\)具有传递性。

计算排列反演表的\(n log( n)\)算法

此题是TAOCP中的5.1.1 Exercise 26
Design an algorithm that computes the inversion table \(b_1 b_2 ... b_n\) corresponding to a given permutation \(a_1 a_2 ... a_n\) of {1,2,3..,n}, where the running time is essentially proportional to \(n log (n)\) on typical computers

书后给出的答案可能需要多读几遍才能理解
基本思路是，按二进制位考察每一个\(a_i\)，从最高位开始，比如计算1到9的排列，则将所有数先分成两组，1，2，……，7为一组，8和9为一组，然后计算不同组数之间的前后关系。同组之间的前后则暂时先不计算。

第二遍，将所有数分成两类，每一类中又分两组，第一类有1，2，3和4，5，6，7两组，第二类有8，9两个数。计算同一类中两组的先后关系，也就是说，4，5，6，7之间的先后暂不计算，但算这4个数和1，2，3之间的先后关系。

第三遍，继续细分成4类 第一类有 两组 1，和2，3, 第二类有4，5，和6，7.第三类有8，9一组
再一遍计算同一类中两组的先后关系。

最后一遍，所有数两两分类：{1},{2,3}{4,5}{6,7}{8,9}每一类中有两个数，计算这两个数的先后关系。

将此4遍的结果加起来，就是最后的结果。


另外其实此题有更直观的解法
先建立空集S, 对排列依次做，取出排列的第i个元素\(a_i\)
求得S中比\(a_i\)大的元素个数\(（rank(a_i)\), 令\({b_a}_i=rank(a_i)\)
将\(a_i\)放入S中

于是问题就转化为，是否有数据结构可以在\(log(n)\)的时间内做到插入和计算rank的操作，这是可能的，只需要简单修改平衡二叉树，例如AVL树，在每个节点保存左右子树的节点数即可。因为AVL的插入和查找都是\(log( n)\)级别的操作。而加上左右子树节点数后，查找操作可以得出当前树中比目标数大的个数的值。