perfect shuffle 算法的一个线性复杂度实现

爱被打了一巴掌 2022-05-21 03:36 40阅读 0赞

<table style="margin:0px; padding:0px; border-collapse:collapse; border-spacing:0px; color:rgb(84,84,84); font-family:Tahoma,'Microsoft Yahei'; font-size:12px; line-height:19px; table-layout:fixed; width:878px; position:relative"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px"> 
 <td style="margin:0px; padding:0px; word-wrap:break-word"> 
 <div style="margin:0px; padding:0px; position:relative; overflow:hidden; height:5178px"> 
 <div style="margin:0px; padding:0px"> 
 
 </div> 
 <div style="margin:0px; padding:0px; min-height:380px; font-size:14px"> 
 今天又发现一个关于完美洗牌的算法。这个比较简单一些，由 microsoft的Peiyush Jain提出。&nbsp; 
 
 原论文：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;A Simple In-Place Algorithm for In-Shuffle. 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Peiyush Jain, Microsoft Corporation. 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;July 2004&nbsp; 
 问题描述：&nbsp; 
 所谓完美洗牌算法即是把输入为:&nbsp; 
 a_1,a_2........a_n,b_1,b_2.........b_n的序列变为&nbsp; 
 b_1,a_1,b_2,a_2.......b_n,a_n 这是in perfect shufle。相对应的还有out perfect shuffle。两者区别在于首尾元素位置变或不变。&nbsp; 
 perfect shuffle算法要求在O(n），时间内，O(1）空间内完成。&nbsp; 
 
 perfect shuffle实质是一个置换。置换为：&nbsp; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i -&gt; 2*i mod (2*n+1)&nbsp; 
 由于置换可以分解为一系列不相交的轮换之积。故如果能找出所有轮换的一个代表元则可很容易解决问题。&nbsp; 
 如&nbsp;&nbsp;&nbsp; 
 n=3时 输入 1&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp;A&nbsp;&nbsp;B&nbsp;&nbsp;C b&nbsp;&nbsp; =&gt; A&nbsp;&nbsp; 1&nbsp;&nbsp; B&nbsp;&nbsp; 2&nbsp;&nbsp; C&nbsp;&nbsp; 3所对应的轮换为（1，2，4）（3，6，5）&nbsp; 
 选代表元为1和3以及一个临时变量T：&nbsp; 
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2-&gt;T,1-&gt;2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
 1&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp; A&nbsp;&nbsp; B&nbsp;&nbsp; C &nbsp;-----------&gt;&nbsp;_&nbsp;&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp; A&nbsp;&nbsp; B&nbsp;&nbsp; C&nbsp; 
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;4-&gt;1,T-&gt;4&nbsp; &nbsp;&nbsp; 
 _&nbsp;&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp; A&nbsp;&nbsp; B&nbsp;&nbsp; C&nbsp;&nbsp;-----------&gt;&nbsp;&nbsp;A&nbsp;&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp; 2&nbsp;&nbsp; B&nbsp;&nbsp; C&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;6-&gt;T,3-&gt;6&nbsp; 
 A&nbsp;&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp; 2&nbsp;&nbsp; B&nbsp;&nbsp; C&nbsp;&nbsp;-----------&gt;&nbsp;A&nbsp;&nbsp;1&nbsp;&nbsp;_&nbsp;&nbsp; 2&nbsp;&nbsp; B&nbsp;&nbsp; 3 
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 5-&gt;3,T-&gt;5&nbsp; 
 A&nbsp;&nbsp;1&nbsp;&nbsp;_&nbsp;&nbsp; 2&nbsp;&nbsp; B&nbsp;&nbsp; 3&nbsp;&nbsp;-----------&gt;&nbsp;A&nbsp;&nbsp;1&nbsp;&nbsp;B&nbsp;&nbsp; 2&nbsp;&nbsp; C&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;置换完成 
 &nbsp; 
 因此问题就转换为求置换的轮换分解中的代表元问题了。&nbsp; 
 文中巧妙的利用特定条件下每个不相交的轮换可有3的不同幂次生成。 
 &nbsp; 
 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 见论文：A Simple In-Place Algorithm for In-Shuffle.&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Peiyush Jain, Microsoft Corporation.&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 1、问题描述：&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 所谓完美洗牌算法即是把输入为:&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> a_1,a_2........a_n,b_1,b_2.........b_n的序列变为&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> b_1,a_1,b_2,a_2.......b_n,a_n&nbsp;这是in perfect shufle。 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> perfect shuffle算法要求在O(n），时间内，O(1）空间内完成。&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> perfect shuffle实质是一个置换。置换为：&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i -&gt; 2*i mod (2*n+1)&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 由于置换可以分解为一系列不相交的轮换之积。故如果能找出所有轮换的一个代表元则可很容易解决问题。&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 如&nbsp;len=3时 输入 1&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp;A&nbsp;&nbsp;B&nbsp;&nbsp;C b&nbsp;&nbsp;&nbsp;=&gt; A&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;B&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;C&nbsp;&nbsp;&nbsp;3所对应的轮换为（1，2，4）（3，6，5）&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 选代表元为1和3以及一个临时变量T：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 1&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;A&nbsp;&nbsp;&nbsp;B&nbsp;&nbsp;&nbsp;C&nbsp;&nbsp;-----------&gt;&nbsp;&nbsp;2-&gt;T,1-&gt;2&nbsp;&nbsp;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> _&nbsp;&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;A&nbsp;&nbsp;&nbsp;B&nbsp;&nbsp;&nbsp;C&nbsp;&nbsp;-----------&gt;&nbsp;&nbsp;&nbsp;4-&gt;1,T-&gt;4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> A&nbsp;&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;B&nbsp;&nbsp;&nbsp;C&nbsp;&nbsp;-----------&gt;&nbsp;6-&gt;T,3-&gt;6&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> A&nbsp;&nbsp;1&nbsp;&nbsp;_&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;B&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;-----------&gt;&nbsp;5-&gt;3,T-&gt;5&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> A&nbsp;&nbsp;1&nbsp;&nbsp;B&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;C&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;置换完成&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 因此问题就转换为求置换的轮换分解中的代表元问题了。&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 文中巧妙的利用特定条件下： 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 即（2的任意次幂）对（3的k次幂）取模，能得到一个轮换环，并且环与环之间刚好互不相交 。&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 如我们分析长度2*n=3^k-1的置换的轮换分解。&nbsp;(若长度为2*4=8，则8=3^2-1) 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 考虑某一包含3^s（ 1 =&lt; s &lt; k ）的轮换。不妨记3^s为a_1，3^k记为m。&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 则轮换里的数分别为：&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;a_2 =&nbsp;&nbsp;2* a_1 mod m&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;a_3 =&nbsp;&nbsp;2* a_2 mod m;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;a_4 =&nbsp;&nbsp;2* a_3 mod m; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;。。。。。&nbsp;。。。 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;a_len = 2* a_len-1 mod m&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> &nbsp;&nbsp;a_1 = 2* a_len &nbsp;&nbsp;mod m&nbsp; 
 <p style="margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 则&nbsp;&nbsp;a_1&nbsp;&nbsp;≡2^len * a_1 mod m;&nbsp;&nbsp;( 最后一项中的a_len用倒数第二行乘2替代，以此类推........)&nbsp;， 
 <p style="margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 依此，假设m=9，可以确定每个轮换中，len的值， 
 <p style="margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 如a_1=3^s=3^0=1，则1=2^len * 1 mod m，则 len=2； 
 <p style="margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 如a_1=3^s=3^1=3，则3=2^len * 3 mod m，则 len=6&nbsp;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 因此每个3^s开始的一个轮换满足&nbsp;:&nbsp;&nbsp; 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 3^s ≡3^s * 2^len mod 3^k&nbsp;,且轮换的长度为len。 
 <p style="margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 补充：若对1 2 3 4 5 6 7 8 9 10进行洗牌则首先交换成 
 <p style="margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 1 2 3 4 6 7 8 9&nbsp;5 10 &nbsp; (n=4，因此我们只对需要的前8个先调整到前面) 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 下面举了个例子：洗牌置换过程例证，它例举了将1234ABCD置换成A1B2C3D4的过程，请将图中的n理解为len，k=2。 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> 
 <p style="color:rgb(73,73,73); margin-top:0px; margin-bottom:20px; padding-top:0px; padding-bottom:0px; border:0px; list-style:none; word-wrap:normal; word-break:normal; line-height:21px; font-family:simsun; font-size:14px; text-align:left"> <a href="http://photo.blog.sina.com.cn/showpic.html#blogid=604d011e0100l9bh&amp;url=http://s13.sinaimg.cn/orignal/604d011e49037e63dd81c" style="color:rgb(60,132,189)" rel="nofollow"><img src="http://s13.sinaimg.cn/middle/604d011e49037e63dd81c&amp;690" alt="完美洗牌算法In-Shuffle" title="完美洗牌算法In-Shuffle" style="margin:0px; padding:0px; border:0px; list-style:none"></a> 
 
 因此很容易得出各轮换的代表元就为3^0,3^1,3^2......3^i(i&lt;k,i+1&gt;k).&nbsp; 
 对于2*n不等于3^k-1的情况，可以巧妙的利用这个结论完成ferfect shuffle。&nbsp; 
 对于2*n不等于3^k-1时，先找一个最接近2*n且比2*n小的2*m=3^k-1。进行如下变换。&nbsp; 
 把序列中m+1到n+m的子序列循环右移m位。&nbsp; 
 A_1,A_2,A_3.......A_m-1,A_m，A_m+1......A_n，A_n+1，A_n＋2，.......A_n+m,A_n+m+1.....A_2*n&nbsp;&nbsp; -&gt;&nbsp; 
 A_1,A_2,A_3.......A_m-1,A_n+1,A_n+2.....A_n+m,A_m,A_m+1......A_n+m+1................A_2*n&nbsp; 
 然后对前2*m子序列进行上面的perfect shuffle。然后对剩下的部分进行同样处理。&nbsp; 
 例如对于长为14的序列进行perfect shuffle置换：&nbsp; 
 输入序列为：&nbsp; 
 1&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp;4&nbsp;&nbsp;5&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;&nbsp;A&nbsp;&nbsp;B&nbsp;&nbsp;C&nbsp;&nbsp;D&nbsp;&nbsp;E&nbsp;&nbsp;F&nbsp;&nbsp;G&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 14=2*7≠3^k.与14最接近的3^k-1是8=3^2 - 1.因此先对4+1到7+4的子序列循环右移4位得：&nbsp; 
 1&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp;4&nbsp;&nbsp;A&nbsp;&nbsp;B&nbsp;&nbsp;C&nbsp;&nbsp;D&nbsp;&nbsp;5&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;&nbsp;E&nbsp;&nbsp;F&nbsp;&nbsp;G&nbsp; 
 对前8位进行perfect shuffle移位后得：&nbsp; 
 A&nbsp;&nbsp;1&nbsp;&nbsp;B&nbsp;&nbsp;2&nbsp;&nbsp;C&nbsp;&nbsp;3&nbsp;&nbsp;D&nbsp;&nbsp;4&nbsp;&nbsp;5&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;&nbsp;E&nbsp;&nbsp;F&nbsp;&nbsp;G&nbsp; 
 剩下的子序列为&nbsp; 
 5&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;&nbsp;E&nbsp;&nbsp;F&nbsp;&nbsp;G&nbsp;&nbsp;&nbsp; 
 长度为6 最接近的2*m1=3^k1-1是 m=1&nbsp; 
 因此对 1+1 到3+1进行循环右移1位得&nbsp; 
 5&nbsp;&nbsp;E&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;&nbsp;F&nbsp;&nbsp;G&nbsp; 
 进行2*m的perfect shuffle后得整个序列为：&nbsp; 
 A&nbsp;&nbsp;1&nbsp;&nbsp;B&nbsp;&nbsp;2&nbsp;&nbsp;C&nbsp;&nbsp;3&nbsp;&nbsp; D&nbsp;&nbsp;4&nbsp;&nbsp; E&nbsp;&nbsp; 5&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp; 7&nbsp;&nbsp; F&nbsp;&nbsp; G&nbsp; 
 剩下的未处理的子序列为：&nbsp; 
 6&nbsp;&nbsp; 7&nbsp;&nbsp; F&nbsp;&nbsp; G&nbsp; 
 同样的循环移位后为：&nbsp; 
 6&nbsp;&nbsp; F&nbsp;&nbsp; 7&nbsp;&nbsp; G&nbsp; 
 进行m=1的perfect shuffle得整个序列为：&nbsp; 
 A&nbsp;&nbsp;1&nbsp;&nbsp;B&nbsp;&nbsp;2&nbsp;&nbsp;C&nbsp;&nbsp;3&nbsp;&nbsp;D&nbsp;&nbsp;4&nbsp;&nbsp;E&nbsp;&nbsp;5&nbsp;&nbsp;F&nbsp;&nbsp;6&nbsp;&nbsp; 7&nbsp;&nbsp;G&nbsp; 
 剩下未处理的子序列为&nbsp; 
 7&nbsp;&nbsp; G&nbsp; 
 长为2的轮换即交换，最后得整个序列为：&nbsp; 
 A&nbsp;&nbsp;1&nbsp;&nbsp;B&nbsp;&nbsp;2&nbsp;&nbsp;C&nbsp;&nbsp;3&nbsp;&nbsp;D&nbsp;&nbsp;4&nbsp;&nbsp;E&nbsp;&nbsp;5&nbsp;&nbsp;F&nbsp;&nbsp;6&nbsp;&nbsp;G&nbsp;&nbsp;7&nbsp; 
 完成perfect shuffle。&nbsp; 
 移位是线性时间，3^k - 1的perfect shuffle置换也是线性时间，最后的递归是对剩下的子序列进行同样的操作，因此整个过程在线性时间内完成。而且需要的辅助空间为常数－个额外临时变量。 
 &nbsp; 
 实现代码： 
 
 <pre><code>#include "stdio.h"
//轮换
void Cycle(int Data[],int Lenth,int Start)
{
 int Cur_index,Temp1,Temp2;

Cur_index=(Start*2)%(Lenth+1);
      Temp1=Data[Cur_index-1];
      Data[Cur_index-1]=Data[Start-1];
   
  while(Cur_index!=Start)
   {
  Temp2=Data[(Cur_index*2)%(Lenth+1)-1];
        Data[(Cur_index*2)%(Lenth+1)-1]=Temp1;
        Temp1=Temp2;
  Cur_index=(Cur_index*2)%(Lenth+1);
   }
}

//数组循环移位 参考编程珠玑
void Reverse(int Data[],int Len)
{
  int i,Temp;
  for(i=0;i&lt;Len/2;i++)
  {
   Temp=Data[i];
   Data[i]=Data[Len-i-1];
   Data[Len-i-1]=Temp;
  }
}
void ShiftN(int Data[],int Len,int N)
{
   Reverse(Data,Len-N);
   Reverse(&amp;Data[Len-N],N);
   Reverse(Data,Len);

}
//满足Lenth=3^k-1的perfect shfulle的实现
void Perfect1(int Data[],int Lenth)
{
     int i=1;

if(Lenth==2)
  {
   i=Data[Lenth-1];
   Data[Lenth-1]=Data[Lenth-2];
   Data[Lenth-2]=i;
   return;
  }
    while(i&lt;Lenth)
 {
     Cycle(Data,Lenth,i);
     i=i*3;
 }
}
   //查找最接近N的3^k
int LookUp(int N)
{
   int i=3;
   while(i&lt;=N+1) i*=3;

if(i&gt;3) i=i/3;

return i;
}

void perfect(int Data[],int Lenth)
{
   int i,startPos=0;
   while(startPos&lt;Lenth)
   {
     i=LookUp(Lenth-startPos);
     ShiftN(&amp;Data[startPos+(i-1)/2],(Lenth-startPos)/2,(i-1)/2);
     Perfect1(&amp;Data[startPos],i-1);
  startPos+=(i-1);
   }
}
#define N 100
 void main()
{
 int data[N]={0};
 int i=0;
 int n;
 printf("please input the number of data you wanna to test(should less than 100):/n");
 scanf("%d",&amp;n);
 if(n&amp;1)
 {
  printf("sorry,the number should be even ");
  return;
 }
 for(i=0;i&lt;n;i++)
  data[i]=i+1;

perfect(data,n);
 for(i=0;i&lt;n;i++)
   printf("%d   ",data[i]);

}</code></pre> 
 
 
 
 </div> 
 </div> </td> 
 </tr> 
 </tbody> 
</table>