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

作者: , 共 2012 字 , 共阅读 0

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 次。
本科同学木瑶的窗子最近写了两篇文章,分别关于机器证明和投票,是这两个话题写的最好的介绍性文章了,分享给大家看一看:
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
给定$ n\times n$ 的实数矩阵,每行和每列都是递增的,求这$ n^2$ 个数的中位数。
风险管理 » VaR Primer
在一个大型的组合中,有成千上万只不同的证券,但不同证券的价格可能受到同样的因素所驱动,比如同一个国家的债券几乎都受到该国的基准利率所影响。为了简化 VaR 的计算,通常将那些最根本的因素挑选出来,这些因素被称为风险因子。根据风险因子的状态,计算证券的价格被称为估值。
相似度: 0.053
今天香港中文大学的Prof. Cai给我们上 graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学方法 :) 。
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
最大回撤是一个重要的风险指标。对于对冲基金和数量化策略交易,这个指标比波动率还重要。
IT » 比特币, 套利交易
最近国内比特币突然大火,国内某交易所的成交量跃居世界第一。但让我倍感迷惑的地方是,目前国内的价格大大高于境外的价格。如下图所示:
IT » 比特币, 数字货币
最近看到一篇文章Satoshi』s Genius: Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets,国内有人翻译过(中本聪的天才:比特币以意想不到的方式躲开了一些密码学子弹)。里面说的第一个就是天才的中本聪并不是将公钥而是将公钥两次 HASH 之后作为比特币账户的地址,这可以让比特币系统抵抗量子计算机的攻击。