关于完美洗牌问题的若干思考

前面学习了完美洗牌问题 

完美洗牌算法学习

又写了一个证明

完美洗牌问题的证明


进一步思考了其他的一些问题：

完美洗牌问题：　给定的输入a1, a2, a3, ……aN, b1,b2,……bN,输出b1,a1,b2,a2,b3,a3…… bN,aN

（1） 如果要求输出是a1,b1,a2,b2……aN,bN怎么办？

这个问题在学习的时候已经考虑过，只是觉得如果先把a部分和b部分交换掉，或者最后再交换相邻的一组两个位置的方法不够美观。

现在想想可以这样，原数组第一个和最后一个不变，中间的2 * (n - 1)项用原始的标准完美洗牌算法做就可以了。

（2） 完美洗牌问题的逆问题：

给定b1,a1,b2,a2,……bN,aN, 输出a1,a2,a3,……aN,b1,b2,b3,……bN

这相当于把偶数位上的数放到一起，奇数位上的数放到一起。

关键问题： 我们需要把cycle_leader算法改一下，沿着圈换回去。改造后的叫reverse_cycle_leader，代码如下：

  1. //逆变换，数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
  2. void reverse_cycle_leader(int *a,int from, int mod) {
  3.     int last = a[from],next, i;
  4.     
  5.     for (i = from;;i = next) {
  6.         next = i * 2 % mod;
  7.         if (next == from) {
  8.             a[i] = last;
  9.             break;
  10.         }
  11.         a[i] = a[next];
  12.         
  13.     }
  14. }

按照完美洗牌算法，我们同样把数分为m和(n - m)两部分。

假设我们把前面若干项已经置换成先a后b的形式了，现在把这m项也置换成先a后b的形式，我们需要把这m项中的a部分换到前面去，这里需要一个循环右移，还要知道以前处理了多长。总之，这个逆shuffle算法需要小心实现一下，代码如下：

  1. //逆shuffle 时间O(n)，空间O(1)
  2. void reverse_perfect_shuffle3(int *a,int n) {
  3. int n2, m, i, k, t, done = 0;
  4.     for (;n > 1;) {
  5.         // step 1
  6.         n2 = n * 2;
  7.         for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3)
  8.             ;
  9.         m /= 2;
  10.         // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1)
  11.         
  12.         for (i = 0, t = 1; i < k; ++i, t *= 3) {
  13.             reverse_cycle_leader(a , t, m * 2 + 1);
  14.         }
  15.         
  16.         if (done) {
  17.             right_rotate(a - done, m, done + m); //移位
  18.         }
  19.         a += m * 2;
  20.         n -= m;
  21.         done += m;
  22.         
  23.         
  24.     }
  25.     // n = 1
  26.     right_rotate(a - done, 1, done + 2);
  27. }

总体算法（含变换和逆变换、还有测试代码）如下，注意所有的下标均从1开始： 

  1. #include 
  2. #include 
  3. #include 
  4. using namespace std;
  5.  
  6. //数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
  7. void cycle_leader(int *a,int from, int mod) {
  8.     int last = a[from],t,i;
  9.     
  10.     for (i = from * 2 % mod;i != from; i = i * 2 % mod) {
  11.         t = a[i];
  12.         a[i] = last;
  13.         last = t;
  14.         
  15.     }
  16.     a[from] = last;
  17. }
  18.  
  19. //翻转字符串时间复杂度O(to - from)
  20. void reverse(int *a,int from,int to) {
  21.     int t;
  22.     for (; from < to; ++from, --to) {
  23.         t = a[from];
  24.         a[from] = a[to];
  25.         a[to] = t;
  26.     }
  27.     
  28. }
  29.  
  30. //循环右移num位 时间复杂度O(n)
  31. void right_rotate(int *a,int num,int n) {
  32.     reverse(a, 1, n - num);
  33.     reverse(a, n - num + 1,n);
  34.     reverse(a, 1, n);
  35. }
  36.  
  37. //时间O(n)，空间O(1)
  38. void perfect_shuffle3(int *a,int n) {
  39.     int n2, m, i, k,t;
  40.     for (;n > 1;) {
  41.         // step 1
  42.         n2 = n * 2;
  43.         for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3)
  44.             ;
  45.         m /= 2;
  46.         // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1)
  47.         
  48.         // step 2
  49.         right_rotate(a + m, m, n);
  50.         
  51.         // step 3
  52.         
  53.         for (i = 0, t = 1; i < k; ++i, t *= 3) {
  54.             cycle_leader(a , t, m * 2 + 1);
  55.             
  56.         }
  57.         
  58.         //step 4
  59.         a += m * 2;
  60.         n -= m;
  61.         
  62.     }
  63.     // n = 1
  64.     t = a[1];
  65.     a[1] = a[2];
  66.     a[2] = t;
  67.     
  68. }
  69.  
  70.  
  71.  
  72. //逆变换，数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
  73. void reverse_cycle_leader(int *a,int from, int mod) {
  74.     int last = a[from],next, i;
  75.     
  76.     for (i = from;;i = next) {
  77.         next = i * 2 % mod;
  78.         if (next == from) {
  79.             a[i] = last;
  80.             break;
  81.         }
  82.         a[i] = a[next];
  83.         
  84.     }
  85. }
  86.  
  87.  
  88. //逆shuffle 时间O(n)，空间O(1)
  89. void reverse_perfect_shuffle3(int *a,int n) {
  90. int n2, m, i, k, t, done = 0;
  91.     for (;n > 1;) {
  92.         // step 1
  93.         n2 = n * 2;
  94.         for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3)
  95.             ;
  96.         m /= 2;
  97.         // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1)
  98.         
  99.         for (i = 0, t = 1; i < k; ++i, t *= 3) {
  100.             reverse_cycle_leader(a , t, m * 2 + 1);
  101.         }
  102.         
  103.         if (done) {
  104.             right_rotate(a - done, m, done + m); //移位
  105.         }
  106.         a += m * 2;
  107.         n -= m;
  108.         done += m;
  109.         
  110.         
  111.     }
  112.     // n = 1
  113.     right_rotate(a - done, 1, done + 2);
  114.     
  115.     
  116. }
  117.  
  118.  
  119. //测试代码
  120. int main() {
  121. const int N = 100000;
  122.  
  123. int a[N * 2 + 1],i;
  124.     for (i = 1; i <= 2 * N; ++i) {
  125.         a[i] = i;
  126.     }
  127.     perfect_shuffle3(a, N);
  128.     reverse_perfect_shuffle3(a, N);
  129.     for (i = 1; i <= 2 * N; ++i) {
  130.         printf("%d\n", a[i]);
  131.     }
  132.     for (i = 1; i <= 2 * N; ++i) {
  133.         if (a[i] != i) {
  134.             puts("NO");
  135.             return 0;
  136.         }
  137.     }
  138.     puts("YES");
  139.     return 0;
  140. }


（3） 如果输入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN，要求输出是c1,b1,a1,c2,b2,a2,……cN,bN,aN怎么办？

这个问题也不是我凭空想像出来的，这是在careercup上看到过的面试题。

我研究了下这个问题，对于任意位置i = 1..3 * N 我们发现

原始1 <= i <= N 时，即a部分， 转移到的位置是 3 * i

原始N < i <= 2 * N 时 即b部分，转移到的位置是 3 * i - (3 * N + 1)

原始2 * N < i <= 3 * N时，即c部分转移到的位置是 3 * i - 2 * (3 * N + 1)

于是我们得到映射位置 i' = i mod (3 * N + 1)

之所以要把a,b,c的顺序反过来，因为有如上这么好的形式。

剩下的问题和学习完美洗牌算法差不多，我们试图对一个特定的长度解决掉。

仿照完美洗牌算法的思路，我验证了3是7的原根，是49的原根，于是3是7^k的原根。于是，我们可以把原来的圈按照截取出一个m，满足3 * m = 7 ^ k - 1，截取出一个m长度后，我们同样需要循环移位，使得(a1..am)(b1..bm)(c1..cm)在一起，这里要循移位两次。算法的步骤如下：

step 1 找到 3 * m = 7^k - 1 使得 7^k <= 3 * n < 7^(k +1)

step 2 把a[m + 1..n + m]那部分循环移m位，再把a[m * 2 + 1..2 * n + m]那部分循环右移m位，这样把数组分成了m和(n - m)两部分。

step 3 对每个i = 0,1,2..k - 1，7^i是个圈的头部，做cycle_leader算法，数组长度为m，所以对3 * m + 1取模。

step 4 对数组的后面部分a[3 * m + 1.. 3 * n]继续使用本算法，这相当于n减小了m。

代码：

  1. //翻转字符串时间复杂度O(to - from)
  2. void reverse(int *a,int from,int to) {
  3.     int t;
  4.     for (; from < to; ++from, --to) {
  5.         t = a[from];
  6.         a[from] = a[to];
  7.         a[to] = t;
  8.     }
  9.     
  10. }
  11.  
  12. //循环右移num位 时间复杂度O(n)
  13. void right_rotate(int *a,int num,int n) {
  14.     reverse(a, 1, n - num);
  15.     reverse(a, n - num + 1,n);
  16.     reverse(a, 1, n);
  17. }
  18.  
  19.  
  20. //数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 3 * n + 1，时间复杂度O(圈长）
  21. void cycle_leader(int *a,int from, int mod) {
  22.     int last = a[from],t,i;
  23.     
  24.     for (i = from * 3 % mod;i != from; i = i * 3 % mod) {
  25.         t = a[i];
  26.         a[i] = last;
  27.         last = t;
  28.         
  29.     }
  30.     a[from] = last;
  31. }
  32.  
  33. //时间O(n)，空间O(1)
  34. void perfect_shuffle3n(int *a,int n) {
  35.     int n3, m, i, k,t;
  36.     for (;n > 2;) {
  37.         // step 1
  38.         n3 = n * 3;
  39.         for (k = 0, m = 1; n3 / m >= 7; ++k, m *= 7)
  40.             ;
  41.         m /= 3;
  42.         // 3m = 7^k - 1 , 7^k <= 3n < 7^(k + 1)
  43.         
  44.         // step 2
  45.         right_rotate(a + m, m, n);
  46.         right_rotate(a + m * 2, m , n * 2 - m);
  47.         
  48.         // step 3
  49.         
  50.         for (i = 0, t = 1; i < k; ++i, t *= 7) {
  51.             cycle_leader(a , t, m * 3 + 1);
  52.             
  53.         }
  54.         
  55.         //step 4
  56.         a += m * 3;
  57.         n -= m;
  58.         //printf("n = %d  m = %d\n",n, m);
  59.         //getchar();
  60.         
  61.     }
  62.     if (n == 2) {
  63.         cycle_leader(a, 1, 7);
  64.     }
  65.     else if (n == 1) {
  66.         t = a[1];
  67.         a[1] = a[3];
  68.         a[3] = t;
  69.     }
  70.     
  71. }



注：本文转载自blog.csdn.net的cpcs的文章"http://blog.csdn.net/caopengcs/article/details/10521603"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！