完美洗牌问题线性算法的两篇论文

作者:, 发表于

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,an,bn\)

那一次讨论我们翻出了问题的来源,一篇长达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\) 的数组 我们可以

  1. 对前一半进行基于 \(2^{N-1}\) 的标准反等差映射置换
  2. 对后一半进行基于 \(2^{N-1}\) 的标准反等差映射置换
  3. 对整体进行基于 \(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\)

这个可以通过三步进行:

  1. 反置 \(A[K]\cdots A[L]\)
  2. 反置 \(B[0]\cdots B[K-1]\)
  3. 反置 \(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.


上一篇:最大回撤和最大短期回撤的线性算法2012年1月8日
最大回撤是一个重要的风险指标。对于对冲基金和数量化策略交易,这个指标比波动率还重要。 最大回撤 定义:对于序列\(x_1,x_2,\cdots,x_n\),定义最

下一篇:计算星期几2016年7月1日
int day_of_week(int y, int m, int d) /* 0 = Sunday */ { static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; y -= m < 3; return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7; }


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。