2007 年，我们讨论过一个算法问题， perfect shuffle ，据称是个微软面试题：
输入$ a1,a2,\cdots,a_n,b_1,\cdots,b_n$ ，如何用$ O(n)$ 的时间，$ O(1)$ 的空间，将这个序列顺序改为 $ a_1,b_1,a_2,b_2,\cdots,a_n,b_n$ 。
那一次讨论我们翻出了问题的来源，一篇长达 12 页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估计贴出来都没几个人仔细看。
这里有两个后续进展：
一周前，老同学 Qingxuan Yang 告诉我他之前想到的一个解法已经写成一篇小论文正式发表：
Qingxuan Yanga, John Ellisb, Khalegh Mamakanib, Frank Ruskey. 2013. In-place permuting and perfect shuffling using involutions. Information Processing Letters. 13 March 2013.
地址：http://www.qingxuanyang.org/download/ShuffleIPLe.pdf
这个想法是在 2008 年 4 月份的一次讨论被提出来，其基本思路是：
这个算法的 核心思想是一个叫做「标准反等差映射」的东西。一个小于$ 2^N$ 的非负整数的标准反等差映射是其末 N 位 2 进制编码的中心对称。
比如 3 对于 16 的标准反等差映射就是 12(0011 –> 1100)。标准反等差映射是 11 对应的 3 和 12 互为基于 16 的标准反等差映射。
那么 对于一个长度为$ 2^N$ 的数组 我们可以
- 对前一半进行基于$ 2^{N-1}$ 的标准反等差映射置换
- 对后一半进行基于$ 2^{N-1}$ 的标准反等差映射置换
- 对整体进行基于$ 2^N$ 进行标准反等差映射置换
结果是对于一个数的下标 X ，如果$ x>=2^{N-1}$ ，$ x\rightarrow 2(x- 2^{N-1}) + 1$ ，否则$ x\rightarrow 2x$ 。
于是对于本问题当数组总长度为$ 2L$ ，$ L = 2^N$ 的特殊情况已经解决。进行$ O(L)$ 次置换，空间复杂度为$ O(1)$ 。
如果认为计算反等差置换所需要的对称值的计算量不是$ O(1)$ 的。可以做一个类累加器的反等差映射下一个生成器，这个每次生成的平均时间复杂度是$ O(1)$ 的。
对于$ L \neq 2^N$ 的情况，我们可以找到小于$ L$ 的最大的$ K$ （$ K = 2^N$ ），然后$ A[K]\cdots A[L]$ ，$ B[0]\cdots B[K - 1]$ 进行一次循环平移，平移量为$ L-K$ 。
这个可以通过三步进行：
- 反置$ A[K]\cdots A[L]$
- 反置$ B[0]\cdots B[K-1]$
- 反置$ B[K-1]\cdots A[K]$
这个也是空间复杂度是$ O(L) $ ， 时间复杂度是$ O(1)$ 的。然后将前一半进行复合标准反等差置换，迭代处理后面$ 2 (L - K)$ 个数。
显然这个算法的时间复杂度是 O(L), 空间复杂度是 O(1)的。
论文还将上面方法的$ 2^N$ 扩充到了任意的$ k^N$ 。
前几天网友 van 提到另外一篇论文：
Jain, Peiyush (May 2008). "A simple in-place algorithm for in shuffles". arXiv:0805.1598.
地址：http://arxiv.org/pdf/0805.1598v1.pdf
这篇文章的方法和上面那个类似，作者发现当$ L=3^N$ ，可以找到简单的算法。剩下的和上面一样。
Q. E. D.
