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

作者: , 共 1740 字

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\) 的数组 我们可以

  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.

类似文章:
珍爱生命,远离政治。我们继续讨论算法。
一个面试题,号称是微软的
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
本科同学木瑶的窗子最近写了两篇文章,分别关于机器证明和投票,是这两个话题写的最好的介绍性文章了,分享给大家看一看:
风险管理 » VaR Primer
在一个大型的组合中,有成千上万只不同的证券,但不同证券的价格可能受到同样的因素所驱动,比如同一个国家的债券几乎都受到该国的基准利率所影响。为了简化 VaR 的计算,通常将那些最根本的因素挑选出来,这些因素被称为风险因子。根据风险因子的状态,计算证券的价格被称为估值。
给定\( n\times n\) 的实数矩阵,每行和每列都是递增的,求这\( n^2\) 个数的中位数。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
相似度: 0.051
今天香港中文大学的Prof. Cai给我们上 graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学方法 :) 。
IT » 比特币, 套利交易
最近国内比特币突然大火,国内某交易所的成交量跃居世界第一。但让我倍感迷惑的地方是,目前国内的价格大大高于境外的价格。如下图所示:
IT » 比特币, 数字货币
最近看到一篇文章Satoshi』s Genius: Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets,国内有人翻译过(中本聪的天才:比特币以意想不到的方式躲开了一些密码学子弹)。里面说的第一个就是天才的中本聪并不是将公钥而是将公钥两次 HASH 之后作为比特币账户的地址,这可以让比特币系统抵抗量子计算机的攻击。