关于完美洗牌问题的若干思考
关于完美洗牌问题的若干思考
发布时间： 6:15:22
编辑：www.fx114.net
本篇文章主要介绍了"关于完美洗牌问题的若干思考"，主要涉及到关于完美洗牌问题的若干思考方面的内容，对于关于完美洗牌问题的若干思考感兴趣的同学可以参考一下。
前面学习了完美洗牌问题&
又写了一个证明
进一步思考了其他的一些问题：
完美洗牌问题：　给定的输入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开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
void reverse_cycle_leader(int *a,int from, int mod) {
int last = a[from],next,
for (i =;i = next) {
next = i * 2 %
if (next == from) {
a[i] = a[next];
按照完美洗牌算法，我们同样把数分为m和(n - m)两部分。
假设我们把前面若干项已经置换成先a后b的形式了，现在把这m项也置换成先a后b的形式，我们需要把这m项中的a部分换到前面去，这里需要一个循环右移，还要知道以前处理了多长。总之，这个逆shuffle算法需要小心实现一下，代码如下：
//逆shuffle 时间O(n)，空间O(1)
void reverse_perfect_shuffle3(int *a,int n) {
int n2, m, i, k, t, done = 0;
for (;n & 1;) {
n2 = n * 2;
for (k = 0, m = 1; n2 / m &= 3; ++k, m *= 3)
// 2m = 3^k - 1 , 3^k &= 2n & 3^(k + 1)
for (i = 0, t = 1; i & ++i, t *= 3) {
reverse_cycle_leader(a , t, m * 2 + 1);
if (done) {
right_rotate(a - done, m, done + m); //移位
a += m * 2;
right_rotate(a - done, 1, done + 2);
总体算法（含变换和逆变换、还有测试代码）如下，注意所有的下标均从1开始：
#include &cstdio&
#include &cstring&
#include &string&
//数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
void cycle_leader(int *a,int from, int mod) {
int last = a[from],t,i;
for (i = from * 2 %i != i = i * 2 % mod) {
//翻转字符串时间复杂度O(to - from)
void reverse(int *a,int from,int to) {
for (; from & ++from, --to) {
t = a[from];
a[from] = a[to];
//循环右移num位 时间复杂度O(n)
void right_rotate(int *a,int num,int n) {
reverse(a, 1, n - num);
reverse(a, n - num + 1,n);
reverse(a, 1, n);
//时间O(n)，空间O(1)
void perfect_shuffle3(int *a,int n) {
int n2, m, i, k,t;
for (;n & 1;) {
n2 = n * 2;
for (k = 0, m = 1; n2 / m &= 3; ++k, m *= 3)
// 2m = 3^k - 1 , 3^k &= 2n & 3^(k + 1)
right_rotate(a + m, m, n);
for (i = 0, t = 1; i & ++i, t *= 3) {
cycle_leader(a , t, m * 2 + 1);
a += m * 2;
a[1] = a[2];
//逆变换，数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
void reverse_cycle_leader(int *a,int from, int mod) {
int last = a[from],next,
for (i =;i = next) {
next = i * 2 %
if (next == from) {
a[i] = a[next];
//逆shuffle 时间O(n)，空间O(1)
void reverse_perfect_shuffle3(int *a,int n) {
int n2, m, i, k, t, done = 0;
for (;n & 1;) {
n2 = n * 2;
for (k = 0, m = 1; n2 / m &= 3; ++k, m *= 3)
// 2m = 3^k - 1 , 3^k &= 2n & 3^(k + 1)
for (i = 0, t = 1; i & ++i, t *= 3) {
reverse_cycle_leader(a , t, m * 2 + 1);
if (done) {
right_rotate(a - done, m, done + m); //移位
a += m * 2;
right_rotate(a - done, 1, done + 2);
//测试代码
int main() {
const int N = 100000;
int a[N * 2 + 1],i;
for (i = 1; i &= 2 * N; ++i) {
perfect_shuffle3(a, N);
reverse_perfect_shuffle3(a, N);
for (i = 1; i &= 2 * N; ++i) {
printf(&%d\n&, a[i]);
for (i = 1; i &= 2 * N; ++i) {
if (a[i] != i) {
puts(&NO&);
puts(&YES&);
（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。
//翻转字符串时间复杂度O(to - from)
void reverse(int *a,int from,int to) {
for (; from & ++from, --to) {
t = a[from];
a[from] = a[to];
//循环右移num位 时间复杂度O(n)
void right_rotate(int *a,int num,int n) {
reverse(a, 1, n - num);
reverse(a, n - num + 1,n);
reverse(a, 1, n);
//数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 3 * n + 1，时间复杂度O(圈长）
void cycle_leader(int *a,int from, int mod) {
int last = a[from],t,i;
for (i = from * 3 %i != i = i * 3 % mod) {
//时间O(n)，空间O(1)
void perfect_shuffle3n(int *a,int n) {
int n3, m, i, k,t;
for (;n & 2;) {
n3 = n * 3;
for (k = 0, m = 1; n3 / m &= 7; ++k, m *= 7)
// 3m = 7^k - 1 , 7^k &= 3n & 7^(k + 1)
right_rotate(a + m, m, n);
right_rotate(a + m * 2, m , n * 2 - m);
for (i = 0, t = 1; i & ++i, t *= 7) {
cycle_leader(a , t, m * 3 + 1);
a += m * 3;
//printf(&n = %d
m = %d\n&,n, m);
//getchar();
if (n == 2) {
cycle_leader(a, 1, 7);
else if (n == 1) {
a[1] = a[3];
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：