完美洗牌：数论+分治+数组循环移动

时间：2016-06-09 20:23 来源：作者：收藏

工具介绍：1. XdebugXdebug是一个开放源代码的PHP程序调试器(即一个Debug工具)，相当强大，它可以用来跟踪，调试和分析PHP程序的运行状况。Xdebug现在的最新版本是Xdebug 2.1.0, 下载页面是 http://xdebug.org/download.php，注意页面中下载链接有多个(如下图

参考
1.完美洗牌算法
2.第三十五章、完美洗牌算法
数论部分请看参考2.

问题

长度为2n的数组{a1,a2,a3,a4,...,an,b1,b2,b3,b4,...,bn}
经过洗牌变为{b1,a1,b2,a2,b3,a3,b4,a4,...,bn,an}
最好要求时间复杂度为O(n)，空间复杂度为O(1)

1 子算法

1.1 最简方法：位置置换

时间O(n),空间O(n)
原始：a1,a2,a3,a4,b1,b2,b3,b4
位置：1, 2, 3, 4, 5, 6, 7, 8
置换：b1,a1,b2,a2,b3,a3,b4,a4
可看出
1->2；
2->4；
3->6；
4->8；
5->1；
6->3；
7->5；
8->7；
通过找规律，得到结论：第i个元素放到第（2*i）%（2*n+1）位置上
注意，若数组下标从0开始，则结论改为：第i个元素放到第(2*i+1)%(2*n+1)位置。

位置置换核心代码：

// 时间复杂度O(n),空间复杂度O(n),数组下标从1开始
// 位置置换，简单实现
void perfect_shuffle1(int* a, int n){
    int* b = new int[n];
    int n2 = n * 2;
    int i;
    for(i = 1; i <= n2; ++i){
        b[(2*i)%(n2+1)] = a[i]; // 将a[i]放置在b[(2*i)%(2*n+1)]上
    }
    for(i = 1; i <= n2; ++i){
        a[i] = b[i]; // 更改原始数组，将b[i]赋值给a[i]
    }
}

注意到
1->2->4->8->7->5->1;
3->6->3；
后面的走圈算法会用到

测试代码如下：

#include <iostream>
using namespace std;

// 数组下标从1开始
// 打印int数组，从1至n
void print_array(int* a, int n){
    for(int i = 1; i <= n; ++i){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 时间复杂度O(n),空间复杂度O(n),数组下标从1开始
// 位置置换，简单实现
void perfect_shuffle1(int* a, int n){
    int* b = new int[n];
    int n2 = n * 2;
    int i;
    for(i = 1; i <= n2; ++i){
        b[(2*i)%(n2+1)] = a[i]; // 将a[i]放置在b[(2*i)%(2*n+1)]上
    }
    for(i = 1; i <= n2; ++i){
        a[i] = b[i]; // 更改原始数组，将b[i]赋值给a[i]
    }
}

int main()
{
    int n = 4;
    int a[9] = {-1, 1,2,3,4,5,6,7,8}; // 数组下标从1开始
    cout << "洗牌前：";
    print_array(a, 2*n);
    perfect_shuffle1(a, n);
    cout << "洗牌后：";
    print_array(a, 2*n);
    return 0;
}

1.2 分治处理：递归置换

时间O(nlogn),空间O(1)（不考虑递归栈空间）
例如，n=4时：
{a1,a2,a3,a4,b1,b2,b3,b4}
交换前半段的后n/2个和后半段的前n/2个，变为：
{a1,a2,b1,b2,a3,a4,b3,b4}
问题规模变为2个子问题，每个子问题中的n变为n/2，直至n=1时为最终的规模，n=0时终止。

n=5时，奇数有特殊处理
{a1,a2,a3,a4,a5,b1,b2,b3,b4,b5}
将中间的放到最后，剩下的前移:
{a1,a2,a3,a4,b1,b2,b3,b4,b5,a5}
变成处理n=4的情况，后面的b5,a5 不动

分治处理核心代码：未用到位置置换，直接采用交换的方式

// 时间复杂度O(nlogn),空间复杂度O(1),数组下标从1开始
// 另一种实现，利用分治，交换位置，未用到位置置换算法
void perfect_shuffle2(int* a, int n){
    int temp, i;

    // 基础情况，n==1，直接交换即可
    if(n == 1){
        swap(a[1], a[2]);
        return;
    }

    int n2 = n * 2; // 数组的实际元素个数（真实长度为2*n+1）
    int n3 = n / 2;
    if(n & 1){ // 奇数情况，a[n]移至最后，其他的元素a[n+1]..a[2*n]前移
        temp = a[n];
        for(i = n + 1; i <= n2; ++i){
            a[i - 1] = a[i];
        }
        a[n2] = temp;
        --n; // 转变为偶数情况，问题规模已经缩小至n-1
    }

    // 偶数情况, 交换前半段的后n/2个和后半段的前n/2个整体交换
    for(i = n3+1; i <= n; ++i){
        swap(a[i], a[i + n3]);
    }

    // 子问题,问题规模折半n->n/2
    perfect_shuffle2(a, n3);
    perfect_shuffle2(a + n, n3);
}

测试代码：

#include <iostream>
#include <algorithm>
using namespace std;

// 数组下标从1开始
// 打印int数组，从1至n
void print_array(int* a, int n){
    for(int i = 1; i <= n; ++i){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 时间复杂度O(nlogn),空间复杂度O(1),数组下标从1开始
// 另一种实现，利用分治，交换位置，未用到位置置换算法
void perfect_shuffle2(int* a, int n){
    int temp, i;

    // 基础情况，n==1，直接交换即可
    if(n == 1){
        swap(a[1], a[2]);
        return;
    }

    int n2 = n * 2; // 数组的实际元素个数（真实长度为2*n+1）
    int n3 = n / 2;
    if(n & 1){ // 奇数情况，a[n]移至最后，其他的元素a[n+1]..a[2*n]前移
        temp = a[n];
        for(i = n + 1; i <= n2; ++i){
            a[i - 1] = a[i];
        }
        a[n2] = temp;
        --n; // 转变为偶数情况，问题规模已经缩小至n-1
    }

    // 偶数情况, 交换前半段的后n/2个和后半段的前n/2个整体交换
    for(i = n3+1; i <= n; ++i){
        swap(a[i], a[i + n3]);
    }

    // 子问题,问题规模折半n->n/2
    perfect_shuffle2(a, n3);
    perfect_shuffle2(a + n, n3);
}

int main()
{
    int n = 4;
    int a[9] = {-1, 1,2,3,4,5,6,7,8}; // 数组下标从1开始
    cout << "洗牌前：";
    print_array(a, 2*n);
    perfect_shuffle2(a, n);
    cout << "洗牌后：";
    print_array(a, 2*n);
    return 0;
}

2 完美洗牌算法

2.1 走圈算法

时间复杂度O（c），c<2*n为圈长，空间复杂度O(1)
1.1 中提到的位置置换算法，经过空间优化可变为走圈算法
n=4时：
1->2->4->8->7->5->1;
3->6->3;
其实就是对1.1中位置置换算法的小部分改进，改进后不必O（n）的空间，只保存并更新一个待置换的中间值即可。
走圈算法核心代码：该方法只能完成一个圈

// 时间复杂度O(c),空间复杂度O(1),数组下标从1开始
// 走圈算法，位置置换算法的空间优化实现
void cycle_leader(int* a, int from, int mod){
    // mod = 2* n + 1
    int last = a[from]; // 待置换的数值
    int temp, i;
    for(i = from * 2 % mod; i != from; i = i * 2 % mod){
        // 为下个待置换的位置
        temp = a[i];
        a[i] = last;
        last = temp;
    }
    a[from] = last;
}

2.2 神级结论

若2n=3k1则可以确定圈的个数，以及每个圈的头部位置。

对于该长度的数组，恰好有K个圈，令i=0,1,...,k1;则各头部位置为3i=1,3,9,...,3k1(注意：位置都是从1开始计数)

若n满足神级结论，则可直接计算。

找k和m关键代码：找到2m=3k1,使得3k≤2n<3k+1

// 时间O(logn)， 空间(1)
// 找满足神级理论的k和m
for(int k = 0, m = 1; 2*n / m >= 3; ++k, m *= 3);
// 循环条件为2n >= 3m时，即2n >= 3^(k+1),此时不满足结论
m /= 2; 
// 注意，在for循环中的m均为m == 3^k, 
//m /= 2后，因为m为3的倍数，在程序中，已经等价于m=(m-1)/2, 所以不用写成m = (m - 1) / 2;

若n不满足，则采用分治思想，将n分成m和n-m两部分，使m满足结论，剩下的n-m重复该过程。

此时，需要数组中间的前部分长为n-m的a段与后部分长为m的b段整体交换，即m+1..n位置与n+1..n+m位置的元素整体交换，相当于把这两段组成的长为n的数组整体循环右移m位。

例如：

a1,a2,...,am,am+1,am+2,...,am+1,am+2,...,an,b1,b2,...,bm,bm+1,bm+2,...,bn

循环右移后：

a1,a2,...,am,b1,b2,...,bm,am+1,am+2,...,am+1,am+2,...,an,bm+1,bm+2,...,bn

此时数组前2m位满足2m=3k1，进行k次走圈，

剩下的位重复此过程，并且不会影响前面的结果。

循环右移关键代码：

// 翻转int数组a，从from至to位置，首尾两两交换
void reverse(int *a, int from, int to)
{
    int temp;
    while(from < to){
        temp = a[from];
        a[from++] = a[to];
        a[to--] = temp;
    }
}

// 循环右移，将int数组a循环右移m位，数组下标从1开始
// XY->YX
// YX == (X'Y')'
void right_rotate(int *a, int n, int m){ // 数据n个，循环m位
    reverse(a, 1, n - m);
    reverse(a, n - m + 1, n);
    reverse(a, 1, n);
}

循环右移测试代码：

#include <iostream>
using namespace std;

// 数组下标从1开始
// 打印int数组，从1至n
void print_array(int* a, int n){
    for(int i = 1; i <= n; ++i){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 翻转int数组a，从from至to位置，首尾两两交换
void reverse(int *a, int from, int to)
{
    int temp;
    while(from < to){
        temp = a[from];
        a[from++] = a[to];
        a[to--] = temp;
    }
}

// 循环右移，将int数组a循环右移m位，数组下标从1开始
// XY->YX
// YX == (X'Y')'
void right_rotate(int *a, int n, int m){ // 数据n个，循环m位
    reverse(a, 1, n - m);
    reverse(a, n - m + 1, n);
    reverse(a, 1, n);
}


int main()
{
    int a[6] = {-1, 1,2,3,4,5}; // 数组下标从1开始
    cout << "循环右移2位前：";
    print_array(a, 5);

    right_rotate(a, 5, 2); // 5个数据，循环右移2位

    cout << "循环右移2位后：";
    print_array(a, 5);

    return 0;
}

2.3 最终完美洗牌算法

算法流程：

输入数组a[1..2n]，问题规模为n

step 1) 找到满足2m=3k1的m，使得3k≤2n<3k+1
step 2) 将数组中间部分a[m+1..n+m]部分循环右移m位
step 3) 分治阶段1，对每个i=0,1,...,k1,3i是每个圈的头部，每个圈做cycle_leader，该部分数组为a[1..2m]，此时问题规模为m，所以cycle_leader中，mod=2*m+1
step 4) 分治阶段2，对数组剩余部分A[2m+1..2n]继续使用该算法，此时问题规模从n降至n-m。

完美洗牌核心代码：

// 时间复杂度O(n), 空间复杂度O(1)，数组下标从1开始
// 完美洗牌算法，
// 若输入：a1 a2 a3 a4 b1 b2 b3 b4
// 则输出：b1 a1 b2 a2 b3 a3 b4 a4，即同编号的b在对应的a前面
void perfect_shuffle3(int *a, int n){
    int n2, m, k, i, temp;
    while(n > 1){
        // step 1
        n2 = n * 2;
        for(k = 0, m = 1; n2 / m >= 3; ++k, m *= 3);
        m /= 2;
        // 2m = 3^k - 1, 3^k <= 2n < 3^(k+1)

        // step 2
        right_rotate(a+m, n, m);

        // step 3
        // 此时temp = 3^i,为每个圈的头部，每次更新至下个置换位置
        for(i = 0, temp = 1; i < k; ++i, temp *= 3){
            cycle_leader(a, temp, m * 2 + 1);
        }

        // step 4
        a += m * 2;
        n -= m;
        // 剩余部分，while继续重复此过程
    }

    // n == 1
    swap(a[1], a[2]);
}

2.3.1 完整实现1 数组下标从1开始的版本：

#include <iostream>
#include <algorithm>
using namespace std;

// 数组下标从1开始
void print_array(int* a, int n){
    for(int i = 1; i <= n; ++i){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 时间复杂度O(c),空间复杂度O(1),数组下标从1开始
void cycle_leader(int* a, int from, int mod){
    // mod = 2* n + 1
    int last = a[from]; // 待置换的数值
    int temp, i;
    for(i = from * 2 % mod; i != from; i = i * 2 % mod){
        // 为下个待置换的位置
        temp = a[i];
        a[i] = last;
        last = temp;
    }
    a[from] = last;
}

// 翻转int数组a，从from至to位置，首尾两两交换
void reverse(int *a, int from, int to)
{
    int temp;
    while(from < to){
        temp = a[from];
        a[from++] = a[to];
        a[to--] = temp;
    }
}

// 循环右移，将int数组a循环右移m位，数组下标从1开始
// XY->YX
// YX == (X'Y')'
void right_rotate(int *a, int n, int m){ // 数据n个，循环m位
    reverse(a, 1, n - m);
    reverse(a, n - m + 1, n);
    reverse(a, 1, n);
}

// 时间复杂度O(n), 空间复杂度O(1)，数组下标从1开始
// 完美洗牌算法，
// 若输入：a1 a2 a3 a4 b1 b2 b3 b4
// 则输出：b1 a1 b2 a2 b3 a3 b4 a4，即同编号的b在对应的a前面
void perfect_shuffle3(int *a, int n){
    int n2, m, k, i, temp;
    while(n > 1){
        // step 1
        n2 = n * 2;
        for(k = 0, m = 1; n2 / m >= 3; ++k, m *= 3);
        m /= 2;
        // 2m = 3^k - 1, 3^k <= 2n < 3^(k+1)

        // step 2
        right_rotate(a+m, n, m);

        // step 3
        // 此时temp = 3^i,为每个圈的头部，每次更新至下个置换位置
        for(i = 0, temp = 1; i < k; ++i, temp *= 3){
            cycle_leader(a, temp, m * 2 + 1);
        }

        // step 4
        a += m * 2;
        n -= m;
        // 剩余部分，while继续重复此过程
    }

    // n == 1
    swap(a[1], a[2]);
}

int main()
{
    int n = 4;
    int a[9] = {-1, 1,2,3,4,5,6,7,8}; // 数组下标从1开始
    cout << "洗牌前：";
    print_array(a, 2*n);

    perfect_shuffle3(a, n);

    cout << "洗牌后：";
    print_array(a, 2*n);

    return 0;
}

2.3.2 完整实现2 数组下标从0开始的版本：

#include <iostream>
#include <algorithm>
using namespace std;

// 完美洗牌，数组下标正常从0开始

// 打印int数组a，a长度为n
void print_array(int* a, int n){
    for(int i = 0; i < n; ++i){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 时间复杂度O(c),空间复杂度O(1)
void cycle_leader(int* a, int from, int mod){
    // mod = 2 * n + 1
    int last = a[from]; // 待置换的数值
    // 规则变为 i->(2*i+1)% (2*n+1)
    for(int i = (from * 2 + 1) % mod; i != from; i = (i * 2 + 1) % mod){
        // i为下个待置换的位置
        swap(a[i], last);

    }
    a[from] = last;
}

// 时间复杂度O(n), 空间复杂度O(1)
// 翻转int数组a，从from至to位置，首尾两两交换
void reverse(int *a, int from, int to)
{
    int temp;
    while(from < to){
        temp = a[from];
        a[from++] = a[to];
        a[to--] = temp;
    }
}

// 时间复杂度O(n), 空间复杂度O(1)
// 循环右移，将int数组a循环右移m位
// XY->YX
// YX == (X'Y')'
void right_rotate(int *a, int n, int m){ // 数据n个，循环m位
    reverse(a, 0, n - m - 1);
    reverse(a, n - m, n - 1);
    reverse(a, 0, n - 1);

}

// 时间复杂度O(n), 空间复杂度O(1)
// 完美洗牌算法，
// 若输入：a1 a2 a3 a4 b1 b2 b3 b4
// 则输出：b1 a1 b2 a2 b3 a3 b4 a4，即同编号的b在对应的a前面
void perfect_shuffle3(int *a, int n){
    int n2, m, k, i, temp;
    while(n > 1){
        // step 1
        n2 = n * 2;
        for(k = 0, m = 1; n2 / m >= 3; ++k, m *= 3);
        m /= 2;
        // 2m = 3^k - 1, 3^k <= 2n < 3^(k+1)

        // step 2
        right_rotate(a+m, n, m);

        // step 3
        // 头部位置变为：temp = 3^i-1,temp更新至下个置换位置
        for(i = 0, temp = 0; i < k; ++i, temp = temp * 3 + 2){
            cycle_leader(a, temp, m * 2 + 1);
        }

        // step 4
        a += m * 2;
        n -= m;
        // 剩余部分，while继续重复此过程
    }

    // n == 1
    swap(a[0], a[1]);
}

int main()
{
    int N = 4;
    int a[8] = {1,2,3,4,5,6,7,8}; // 数组下标从0开始

    cout << "洗牌前：";
    print_array(a, 2*N);

    perfect_shuffle3(a, N);

    cout << "洗牌后：";
    print_array(a, 2*N);

    return 0;
}