现在的位置: 首页 > 综合 > 正文

关于完美洗牌问题的若干思考 关于完美洗牌问题的若干思考关于完美洗牌算法中圈和圈起点的一个证明

2017年09月27日 ⁄ 综合 ⁄ 共 9425字 ⁄ 字号 小 中 大 ⁄ 评论关闭

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

分类： 好玩的算法2013-08-29
18:10 1212人阅读 评论(0) 收藏 举报

前面学习了完美洗牌问题 

完美洗牌算法学习

又写了一个证明

完美洗牌问题的证明

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

完美洗牌问题：　给定的输入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，代码如下：

[cpp] view
plaincopy

  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算法需要小心实现一下，代码如下：

[cpp] view
plaincopy

  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开始：

[cpp] view
plaincopy

  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <string>  
  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. }  
  141.      

（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。

代码：

[cpp] view
plaincopy

  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. }  
  72.  

    关于完美洗牌算法中圈和圈起点的一个证明

    分类： 好玩的算法2013-08-28
    11:03     714人阅读 评论(0) 收藏 举报
    算法

    我们用mod表示对一个数取余数，例如3 mod 5 = 3,  5 mod 3 = 2……   a mod b = a - [a / b] * b。

    在完美洗牌算法中，我们用到了一个映射关系  i' = (i * 2) mod (2n + 1)  其中i = 1,2,3,...2n 然后我们对2m = (3^k - 1) 开始找圈了，这个结论的证明还是需要一些数论的基础。现在简要介绍一下，其中一个定理(*)的证明还是稍显复杂，不过可以可以查到。 

    先把我们要证的结论用白话形容一下，

    我们证明  M = 2m = 3^k - 1的情况下, i' = (i * 2) mod (M + 1) = (i * 2) mod (3^k) ，按照这个置换恰好形成k个圈，每个圈的头部（最小的数）是1,3,9,..3^(k - 1)。 （k >= 1)。证明的关键是这所有的圈合并必须包含全部从1到M之间的整数，一个都不能少。

    要证这个结论，先要对原根有一个感性的认识。

    一个数g，是另外一个数x的原根，是说集合S = {g ^ 0 mod x, g ^ 1 mod x, g ^ 2 mod x…… }，得到的集合包含了所有小于x并且与x互质的数。

    这里S看起来像一个无限集合，实际上它是有限的。这是因为我们对x取余数，所以最多只有0到(x - 1)这x种结果。

    举例，比如2是3的原根

    因为2^0 mod 3 = 1, 2 ^ 1 mod 3 = 2, 2 ^ 2 mod 3 = 1, 2 ^ 3 mod 3 = 2....只有{1,2}两种结果，而且和3都互质。

    而2不是7的原根，

    这是因为2^0 mod 7 = 1, 2 ^ 1 mod 7 = 2, 2 ^ 2 mod 7 = 4, 2 ^ 3 mod 7 = 1 只有{1,2,4} 3种结果而没包含3，5，6。

    为了方便还是先定义欧拉函数phi(x)， 也有用希腊字母φ(x)表示的，表示不超过x的整数种和x互质的个数，特别地，当p是质数的时候因为所有小于p的数都与p互质，所以phi(p) = p - 1。

    那么数g，是x的原根，表示为集合S = {g ^ 0 mod x, g ^ 1 mod x, g ^ 2 mod x,……}  恰好包含phi(x)个整数。

    首先，要判断原根g是x的原根，一个必要条件是g与x必须互质。否则g ^ 1 mod x 产生的数就不和x互质了。

    我们之所以取g ^ 0 = 1 是为了方便。

    如果我们在g ^ 0 mod x, g ^ 1 mod x, g ^ 2 mod x……这一串数中发现重复的余数，g ^ i mod x = g ^ j mod x 并且 i < j， 则有g ^ (j - i) mod x = 1  = g ^ 0 mod x (一般同余不能两遍随便做除法，但是互质的时候可以除）。这就说明在比j更早的时候，(j - i)时我们已经发现了重复的余数1了。也就是说当g与x互质的时候，按g
    ^ 0 mod x, g ^ 1 mod x,……的顺序，如果第一次发现重复，重复的数必定是1，这是我们从g^0开始计算的原因。出现余数循环一定是从开头循环的。这对我们要证明的结论至关重要，只看集合里元素的种类数是不够的。

    比如不互质的时候 ，结论不一定正确，g = 9, x = 15, 9 ^ 0 mod 15 = 1, 9 ^ 1 mod 15 = 9, 9 ^ 2 mod 15 = 6, 9 ^ 3 mod 15 = 9, 我们发现9 ^ 3和9 ^ 1出现循环，并没有从开头的1开始循环。 

    有一个著名的定理叫做费马小定理，它告诉我们当g与x互质的时候，有g ^ phi(x) mod x = 1。

    结合原根的定义还有前面的结论，我们要证集合S恰好包含phi(x)个数，只需要证明{g ^ 0 mod x, g ^ 1 mod x ,……g ^ (phi(x) - 1) mod x} 这些数都不相同就可以了。

    我们不加证明的给出如下结论：

    p是奇素数，如果g是p的原根且g ^ (p - 1)  mod p ^ 2 != 1，则g是任意p^k的原根。(k >= 1)

    p是奇素数，如果g是p ^ 2的原根， 则g是任意p^k的原根。 (k >= 1) 

    这两个定理的描述和证明可参看

    http://people.math.gatech.edu/~mbaker/pdf/primroots.pdf

    http://en.wikipedia.org/wiki/Primitive_root_modulo_n

    取g = 2, p = 3。

    我们知道2是3的原根，2是9的原根。

    我们定义S(k)表示上述的集合S，并且x = 3 ^ k。

    所以S(1) = {1, 2}

          S(2) = {1, 2, 4, 8, 7, 5}

    我们没改变圈元素的顺序，由前面的结论S(k)恰好是一个圈里的元素，且认为从1开始循环的，也就是说从1开始的圈包含了所有与3 ^ k互质的数。 

    那与3 ^ k不互质的数怎么办？如果0 < i < 3 ^ k与 3 ^ k不互质，那么它与3 ^ k的最大公约数一定是3 ^ t的形式（只包含约数3),并且 t < k。即gcd(i , 3 ^ k) = 3 ^ t

    我们把3 ^ t除下去，有gcd(i / (3 ^ t), 3 ^ (k - t))  = 1， i / (3 ^ t) 都与3 ^ (k - t) 互质了，并且i / (3 ^ t) < 3 ^(k - t), 根据定义，可见i / (3 ^ t) 在集合S(k - t)。 同理，任意S(k - t)中的数x，都满足gcd(x , 3 ^ k)  = 1,于是gcd(3 ^ k , x * 3 ^ t) = 3
    ^ t, 并且x * 3 ^ t < 3 ^ k。可见S(k - t)中的数x * 3 ^ t 与 i形成了一一对应的关系。请仔细体会这种一一对应的关系。

          也就是说S(k - t)里每个数x * 3 ^ t形成的新集合包含了所有与3 ^ k的最大公约数为3 ^ t的数，它也是一个圈,原先圈的头部是1，这个圈的头部是3 ^ t。

    于是，对所有的小于 3 ^ k的数，根据它和3 ^ k的最大公约数，我们都把它分配到了一个圈里去了。k个圈包含了所有的小于3^k的数。

    举例：

    比如k = 3。 我们有：

            S(3) = {1, 2 ,4 , 8, 16, 5, 10, 20, 13, 26, 25, 23, 19, 11, 22, 17, 7, 14} 包含了小于27且与27互质的所有数，圈的首部为1，这是原根定义决定的。

            那么与27最大公约数为3的数，我们用S(2)中的数乘以3得到。 S(2) * 3 = {3, 6, 12, 24, 21, 15}, 圈中元素的顺序没变化，圈的首部是3 

                   与27最大公约数为9的数，我们用S(1)种的数乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的顺序没变化，圈的首部是9。

    因为每个小于27的数和27的最大公约数只有1, 3, 9这3种情况，又由于前面所证的一一对应的关系，所以S(2) * 3包含了所有小于27且与27的最大公约数为3的数，S(1) * 9 包含了所有小于27且和27的最大公约数为9的数。


返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞