||
紧张的工作暂时告一段落,心情也倍儿愉快。傍晚在公交车上,晃悠中莫名回想起了前阵子工作中所写程序的一些片段,好些都是值得深思并令人愉快的。下文是其中一个片段的一些相关联想。
简单的有如下的两个序列:
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年后才意识到……。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-26 04:49
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社