紧张的工作暂时告一段落，心情也倍儿愉快。傍晚在公交车上，晃悠中莫名回想起了前阵子工作中所写程序的一些片段，好些都是值得深思并令人愉快的。下文是其中一个片段的一些相关联想。

简单的有如下的两个序列：

k1 =

    1     2    3     4     5    6     7     8    9

k2 =

    2     5    1     8     3    4     9     7    6

k1是1:9的连续序列，k2是一个被打乱顺序的1:9序列。把k2中的元素以怎样的顺序安排可以得到k1？

rp2=

    3    1     5     6    2     9     8    4     7

以rp2所列顺序，即k2[3]、k2[1]、……k[7]排列便可以得到序列k1。如何得到rp？最早接触这个问题应是小学吧，而且不是相关在数学科目上，反而是在语文课上，不知道大家还记得排列几句话，大约是以因果、语境、时间等规则组合成一个段落，写下句子排列的顺序。若k2就是被打散的段落，即第2句被放在第1个位置，第5句放在第2位置……，那么这道习题的答案就是rp2了，当然很少有人在做这道题的时候会把隐含的k2顺序给列出来，那时我常强迫症似的写下k2，考试时一慌张还真的不知道该写哪个了。

      k1、k2、rp2的关系：k1以rp2的顺序放置可以得到k2，也可以认为k1以k2的顺序放置可以得到rp2，或者k2[rp2]= 1:9，或者rp2[k2]=1:9……。那时想来，对于这类语文习题都是在问“打乱的句子以何种顺序可以组合得到完整的段落”，那么应该都解释得通的。不去纠结了，毕竟这不是本文主要想要写的内容。

现讨论下面一个问题，若有序列k3

k3 =

    4     2    6     9     7    1     3     8    5

      当有序列k2时，如何得到序列k3呢？对于这个问题简单的解答是：在k2 find k3[1] 得到位置6那么写下result[1] = 6，在 k2 find k3[2] 得到位置1那么写下 result[2] = 1，如此反复得到序列result使k2[result] = k3。也许在学习线代之前，或许完全没有可能意识到这不是个好方法，我们可以简单分析这个算法的时间复杂度是O(n^2)。为何说这不是个好方法呢，因为有信息这种方式下我们没有利用到，k2,k3元素是可以建立双射的一一对应的。

      其实从列k2得到序列k3，这应是搜寻匹配算法的研究的一部分。为了得到一个好些的算法，做下面的分析：同k2得到rp2的方法，也可以从k3得到rp3。以rp2[k2]=1:9在O(n)的时间下得到kx ->rpx的转换。

rp3 =

    6    2     7     1    9     3     5    8     4

以k2我们可以生成酉矩阵L2

Matlab程序：

>>n=9;

>>L2=zeros(n,n);

>>L2((k2-1)*n+k1)=1

>>L2 =

    0    1     0     0    0     0     0    0     0

    0    0     0     0    1     0     0    0     0

    1    0     0     0    0     0     0    0     0

    0    0     0     0    0     0     0    1     0

    0    0     1     0    0     0     0    0     0

    0    0     0     1    0     0     0    0     0

    0    0     0     0    0     0     0    0     1

    0    0     0     0    0     0     1    0     0

    0    0     0     0    0     1     0    0     0

由Lx*Lx'=I 推知L2每行为一的位置就是序列k2，L2每列为一的位置就是rp2。

即： k1*L2’ = k2；  k1*L2 = rp2；

       k1*L3’ = k3；   k1*L3 = rp3；

那么有： k2*L2*L3’ = k3；=> k2(rp2(k3)) = k3

即对k2以序列 re =rp2(k3) 规则可得到k2(re) = k3。

整个个过程以matlab语言描述：

>> k1

k1 =

    1    2     3     4     5    6     7     8    9

>> k2

k2 =

    2    5     1     8    3     4     9    7     6

>> k3

k3 =

    4    2     6     9    7     1     3    8     5

>>rp2=zeros(1,9);

>>rp2(k2)=1:9

rp2 =

    3    1     5     6    2     9     8    4     7

>>re=rp2(k3)

re =

    6    1     9     7    8     3     5    4     2

>> k2(re)

ans =

    4    2     6     9    7     1     3    8     5

从k2到k3的映射位置得到规则re，需要的算法时间O(n)即可。同理k3-> k2的规则：rp3(k2)。

对于rpx，我们可以认为建立了一个hash，在序列表是一个由一些符号做为索引时，我们只要以某种规则建立的hash，如在上述问题中，就是以1:9做为规则建立原形k2的hash：rp2。

****************************************************************************************

原来在小学时的语文课上做了有生以来第一个矩阵逆。20年后才意识到……。