Perfect Shuffle的算法

zhiqiang四月 1, 2008 计算机科学

珍爱生命，远离政治。我们继续讨论算法。

2008/04/01补充：此算法有重大缺陷。详情请见留言部分。

一年前，我们讨论过一个算法问题，perfect shuffle，据称是个微软面试题：

输入a_1,a_2,\cdots,a_n,b_1,\cdots,b_n，如何用O(n)的时间，O(1)的空间，将这个序列顺序改为a_1,b_1,\cdots,a_n,b_n。

那一次讨论我们翻出了问题的来源，一篇长达12页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估计贴出来都没几个人仔细看。

这一次，Xie Xie（没错，又是他 :) ）翻出了Art of Computer Programming, Volume 3上的一个难度为40分的Merge Sort习题：

已知数列x_1\leq x_2\leq \cdots x_M, x_{M+1}\leq x_{M+2}\leq\cdots\leq x_n，设计算法使得在线性时间，常数空间实现归并，也就是将原数组排序。

而Perfect Shuffle问题是可以规约到这个Merge Sort问题的：

mergeSort(x[1...2n]); // if this function solve Merge Sort problem
perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem
     m <- max(x[1...2n])+1;
     x[i] <- x[i]+(2i-1)m,
     x[i+n] <- x[i+n] + 2im
     mergeSort(x[1...2n])
     x[i] <- x[i]%m

原来我还不相信这个问题会是一个面试题。现在我信了。因为那个归并排序的算法还是有些牛人会知道的。

很好很强大。

 

另注：从2006年4月1号愚人节开始，阅微堂成立两周年了。

过去一年，阅微堂共发表了201篇文章，其中包括Liu Tao先生的19篇文章，sog white的17篇文章，以及一些授权转载的网友原创作品。共3389条留言。

感谢大家的关注和对阅微堂的支持。

关于, , , »
  • 一个算法面试题 & 面试题库 一个面试题，号称是微软的 输入$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$$，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为$$a_1, b_1, ..., a_n, b_n$$。 刚一...
  • 帽子游戏二 这个题目听说是MSRA的面试题。 在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...
  • 求平方根倒数的算法 下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x...
  • Google的疯狂面试题 有一些是火星题，比如最后一个海盗分金，不太可能还用来作为面试题，估计是被拉过来凑数的。 原文（英文）直接到这里看吧，27floors给出了中文翻...
  • 一个简单图的三染色算法问题 注: 这个问题来自China Theory Week 2008的Open Problems Session。 我们知道在数学里证明一个东西的存在性的时候，有时候只证明了“存在性”，而且在证明过程...
  • 魔方里的数学 今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学...
  • 2008年10月EMC笔试 今天下午去EMC笔试了。笔试题目分四部分：求职意向3题，专业基础知识和智力题25道，编程题3道，英语作文。全英文题目和作答。虽然前面关于操作系...
  • 阅微堂一周年 从去年4月1号愚人节开始，阅微堂成立一周年了。 过去一年，阅微堂共发表了226篇文章，其中包括Liu Tao先生的21篇文章，sog white的50篇文章，以及一些...
  • 有序矩阵的中位数算法 给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。 使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...
  • 算法百科全书 - Encyclopedia of Algorithms Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。 翻了一下，...
18条留言 -> 跳到留言表格
  • At 2008.04.01 10:51, roy_hu said:

    虽然如此，复杂程度并没有降低啊。还是一个论文级别的题目。最早由Kronrod解决，题为“An Optimal Ordering Algorithm Without a Field of Operation”，原文似已不可考。

    [Reply]
    • At 2008.04.01 19:52, zhiqiang said:

      我提到的那篇论文的方法非常复杂，面试的时候不可能想出来。而且实际空间复杂度是O(\log n\log\log n)。

      [Reply]
      • At 2008.04.01 21:48, Think said:

        那个人好像是个俄罗斯人
        M A Kronrod, "An Optimal Ordering Algorithm without a Field of Operation," Dok Akad Nauk SSSR 186 (1969), 1256-1258
        杂志是俄文的:-)

        [Reply]
      • At 2008.04.01 15:01, dstyler said:

        阅微堂,见微知著，哈哈

        [Reply]
        • At 2008.04.01 19:08, haha said:

          你的规约改写了x数组的值。
          如果可以改写的话，O(1)空间O(N)时间的算法是显然的。

          [Reply]
          • At 2008.04.01 22:04, Think said:

            你说的办法是否是这样：
            每个元素进行了改写，意味着它带了一附加的信息即下标。
            然后再用生成元的办法。
            如果某位置的元素所携带下标是它应该放置的位置，如2位置已经放的是b_1了，则不动；反之利用这个元素一直push它后面乘2加1的元素直到返回此点。
            这就是加了一个bool标记。

            请问haha同学是？

            [Reply]
            • At 2008.04.01 22:37, zhiqiang said:

              对的. 经过改写后, 增加了附加信息, 已经相当于使用了更多的空间.

              所以文章中写的规约的算法不能算一个解法. 这次无意中弄出了一个愚人节笑话, :han

              [Reply]
            • At 2008.04.07 16:28, lemonutzf said:

              呵呵。我觉得规约没有什么问题。 如果归并可解，那么shuffle一样可解，而且复杂度一样，并不需要更多的空间。唯一的担忧是x[i]+(2i-1)m这样的数有可能导致整型表示溢出。不过，如果从纯数学的角度来讲，这个担忧是没必要地。
              问题是出在归并是不可解的，在你要求的复杂度内。
              这是个解的悖论。事实上，shuffle是归并的子问题。也就是说shuffle解的复杂度一定会小于等于归并解的复杂度。而你在千方百计之后子问题解的复杂度依然没将下来的时候，妄图用更大问题的解的特殊化来降低复杂度，确实是开了个玩笑。

              [Reply]
              • At 2008.04.07 20:36, zhiqiang said:

                为什么规约无效，见Think网友的留言。

                至于那个归并问题，是可以在线形时间常数空间内解决的。这是算法编程艺术上的一个40分的习题，难度很大，但确实是可以解的。

                [Reply]
                • At 2008.04.09 17:35, lemonutzf said:

                  首先很高兴能跟你探讨这个问题，因为这个问题我也考虑很久了。一直让我很烦躁，吼吼。
                  Think网友的留言，并不能推翻你的规约。因为你的规约确实没有消耗多余的空间，唯一的只是多了个变量m。我还是挺同意think的这句话：“每个元素进行了改写，意味着它带了一附加的信息即下标。（实际上是为了用merge来解）”，不过， 虽然是附加了个下标，但是这个规约巧妙的把下标叠加到原有信息，没有浪费多余空间。而且最后还复原回来了，嘿嘿。 而think网友的这句话就完全没有逻辑，说明他没好好看规约程式：“然后再用生成元的办法。如果某位置的元素所携带下标是它应该放置的位置，如2位置已经放的是b_1了，则不动；反之利用这个元素一直push它后面乘2加1的元素直到返回此点。这就是加了一个bool标记。” 什么生成元算法，这在规约中根本就没有体现出来。规约在叠加之后就把问题抛给merge，也就是说你merge爱咋地咋地吧，反正只要你在我要求的时间空间内完成，我就能完成。
                  关于merge，我看了艺术。确实可解。而且在69年就解了。牛人太多了。呵呵。不过69解倒是给了我启发，想到shuffle问题一个解法，举例说明如下：
                  初始： a1,a2,a3,a4, | b1,b2,b3,b4
                  折半交换：a1,a2,b1,b2, | a3,a4,b3,b4
                  隔一叠加左到右：a1,a2,b1,b2, | a1+a3,b1+a4,a2+b3,b2+b4
                  隔一消减：a3,b3,a4,b4, | a1+a3,b1+a4,a2+b3,b2+b4
                  隔一再消减：a3,b3,a4,b4, | a1,b1,a2,b2
                  交换前后得解：a1,b1,a2,b2, | a3,b3,a4,b4
                  （此解法主要用到了这个交换程式：#define swap(a,b) a=a+b;b=a-b;a=a-b;）

                  [Reply]
                  • At 2008.04.09 20:46, zhiqiang said:

                    Think的后一句话是在允许修该数组元素的情况下给出的另一个算法，而不是文中算法的阐述。

                    Think的意思是： 如果允许文中的规约，根本不需要复杂的mergeSort算法，可以直接“如果某位置的元素所携带下标是它应该放置的位置，如2位置已经放的是b_1了，则不动；反之利用这个元素一直push它后面乘2加1的元素直到返回此点。”。这个其实在上次讨论的时候我们就已经发现了，这次太兴奋了，一下子就忘记了。

                    不过你的算法还是目前为止最好的，文中的规约太容易越界，你这个就好得多。good job :D

                    [Reply]
                    • At 2008.04.10 10:30, zhiqiang said:

                      我仔细看了你下你的算法，似乎有问题。你的第三步，第四部，第五步其实就是一个交换嘛，根本不需要做什么加加减减的。

                      所以算法有点问题，你写一个16个数的例子看看？

                      [Reply]
                      • At 2008.04.10 10:48, lemonutzf said:

                        嗯。你指出了要害。确实有问题。 6个数的时候就可以看出来。- -. 不知此路是否还行的通。。

                        [Reply]
                        • At 2008.04.10 11:09, Think said:

                          昨晚睡觉的时候觉得不对，可惜上床了，今天过来一看zhiqiang已经抢先了。时差啊，时差。

                      • At 2008.04.12 16:42, szuxjq said:

                        不做加加减减，这样就是O(nlgn)了。这样挺简单的，不过还是达不到线性。

                        [Reply]
                    • At 2008.04.09 19:39, lemonutzf said:

                      关于解法的详细内容见：
                      http://lemonutzf.spaces.live.com/blog/cns!ABF7C5FC3A1AC14B!331.entry

                      [Reply]
                  • At 2008.04.10 01:34, Think said:

                    用加减法还不如用异或呢，呵呵，更不容易越界。

                    [Reply]
                    • At 2008.04.10 10:16, lemonutzf said:

                      XOR is better

                      [Reply]
                      (Required)
                      (Required, not published)

                        B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?
                      «
                      »
                      guest | 注册 | BBS | 管理 | English | 繁體 | https

                      阅微堂

                      zhiqiang's personal blog
                      Loading...
                      Loading...
                      Loading...