【编程之美】一摞烙饼的排序

一，问题：

星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？”

你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？（参考flyingherts的专栏）

二，分析：

n个烙饼经过翻转后的所有状态可组成一棵树。寻找翻转最少次数，相当于在树中搜索层次最低的某个节点。

由于每层的节点数呈几何数量级增长，在n较大时，使用广度优先遍历树，可能没有足够的内存来保存中间结果（考虑到每层的两个节点，可以通过旋转，移位等操作互相转换，也许每层的状态可以用一个函数来生成，这时可以采用广度优先方法），因而采用深度优先。但这棵树是无限深的，必须限定搜索的深度（即最少翻转次数的上限值），当深度达到该值时不再继续往下搜索。最少翻转次数，必然小等于任何一种翻转方案所需的翻转次数，因而只要构造出一种方案，取其翻转次数即可做为其初始值。最简单的翻转方案就是：对最大的未就位的烙饼，将其翻转，再找到最终结果中其所在的位置，翻转一次使其就位。因此，对编号在n-1和2之间的烙饼，最多翻转了2*(n-2)次，剩下0和1号烙饼最多翻转1次，因而最少翻转次数的上限值是：2*(n-2)+1=2*n-3（从网上可搜索到对该上限值最新研究结果：上限值为18/11*n），当然，最好还是直接计算出采用这种方案的翻转次数做为初始值。

三，减少遍历次数：

1 ）减小“最少翻转次数上限值”的初始值，采用前面提到的翻转方案，取其翻转次数为初始值。对书中的例子{3,2,1,6,5,4,9,8,7,0}，初始值可以取10。

2 ） 避免出现已处理过的状态一定会减少遍历吗？答案是否定的，深度优先遍历，必须遍历完一个子树，才能遍历下一个子树，如果一个解在某层比较靠后位置，若不允许处理已出现过的状态时，可能要经过很多次搜索，才能找到这个解，但允许处理已出现过的状态时，可能会很快找到这个解，并减小“最少翻转次数的上限值”，使更多的分支能被剪掉，反而能减少遍历的节点数。比如说，两个子树A、B，搜索子树A，100次后可得到一个对应翻转次数为20的解，搜索子树B，20次后可得到翻转次数为10的解，不允许处理已出现过的状态，就会花100次遍历完子树A后，才开始遍历B，但允许翻转回上一次状态，搜索会在A、B间交叉进行，就可能只要70次找到子树B的那个解（翻转次数为10+2=12），此时，翻转次数上限值比较小，可忽略更多不必要的搜索。以书中的{3,2,1,6,5,4,9,8,7,0}为例，按程序（1.3_pancake_1.cpp），不允许翻转回上次状态时需搜索195次，而允许翻转回上次状态时只要搜索116次。

3） 如果最后的几个烙饼已经就位，只须考虑前面的几个烙饼。对状态(0,1,3,4,2,5,6)，编号为5和6的烙饼已经就位，只须考虑前5个烙饼，即状态(0,1,3,4,2)。如果一个最优解，从某次翻转开始移动了一个已经就位的烙饼，且该烙饼后的所有烙饼都已经就位，那么对这个解法，从这次翻转开始得到的一系列状态，从中移除这个烙饼，可得到一系列新的状态。必然可以设计出一个新的解法对应这系列新的状态，而该解法所用的翻转次数不会比原来的多。

4 ）估计每个状态还需要翻转的最少次数（即下限值），加上当前的深度，如果大等于上限值，就无需继续遍历。这个下限值可以这样确定：从最后一个位置开始，往前找到第一个与最终结果位置不同的烙饼编号（也就是说排除最后几个已经就位的烙饼），从该位置到第一个位置，计算相邻的烙饼的编号不连续的次数，再加上1。每次翻转最多只能使不连续的次数减少1，但很多人会忽略掉这个情况：最大的烙饼没有就位时，必然需要一次翻转使其就位，而这次翻转却不改变不连续次数。（可以在最后面增加一个更大的烙饼，使这次翻转可以改变不连续数。）如：对状态(0,1,3,4,2,5,6)等同于状态(0,1,3,4,2)，由于1、3和4、2不连续，因而下限值为2+1=3。下限值也可以这样确定：在最后面增加一个比所有烙饼都大的已经就位的烙饼，然后再计算不连续数。如：(0,1,3,4,2)，可以看作(0,1,3,4,2,5)，1和3 、4和2 、2和5这三个不连续，下限值为3。

5）多数情况下，翻转次数的上限值越大，搜索次数就越多。可以采用贪心算法，通过调整每次所有可能翻转的优先顺序，尽快找到一个解，从而减少搜索次数。比如，优先搜索使“下限值”减少的翻转，其次是使“下限值”不变的翻转，最后才搜索使“下限值”增加的翻转。对“下限值”不变的翻转，还可以根据其下次的翻转对“下限值”的影响，再重新排序。由于进行了优先排序，翻转回上一次状态能减少搜索次数的可能性得到进一步降低。

6 ）其它剪枝方法：

假设进行第m次翻转时，“上限值”为min_swap。

如果翻转某个位置的烙饼能使所有烙饼就位（即翻转次数刚好为m），则翻转其它位置的烙饼，能得到的最少翻转次数必然大等m，因而这些位置都可以不搜索。

如果在某个位置的翻转后，“下限值”为k，并且 k+m>=min_swap，则对所有的使新“下限值”kk大等于k的翻转，都有 kk+m>=min_swap，因而都可以不搜索。该剪枝方法是对上面的“调整翻转优先顺序”的进一步补充。

另外，翻转某个烙饼时，只有两个烙饼位置的改变才对“下限值”有影响，因而可以记录每个状态的“下限值”，进行下一次翻转时，只须通过几次比较，就可以确定新状态的“下限值”。（判断不连续次数时，最好写成 -1<=x && x<=1， 而不是x==1 || x==-1。对于 int x; a<=x && x<=b，编译器可以将其优化为 unsigned (x-a) <= b-a。）

结果：

对书上的例子{3,2,1,6,5,4,9,8,7,0}：

	翻转回上次状态	搜索函数被调用次数	翻转函数被调用次数
1.3_pancake_2	不允许	29	66
1.3_pancake_2	允许	33	74
1.3_pancake_1	不允许	195	398
1.3_pancake_1	允许	116	240

（这个例子比较特殊，代码1.3_pancake_2.cpp（与1.3_pancake_1.cpp的最主要区别在于，增加了对翻转优先顺序的判断，代码下载），在不允许翻转回上次状态且取min_swap的初始值为2*10-2=18时，调用搜索函数29次，翻转函数56次）。

搜索顺序对结果影响很大，如果将1.3_pancake_2.cpp第152行：

for (int pos=1, last_swap=cake_swap[step++]; pos<size; ++pos){

这一行改为：

for (int pos=size-1, last_swap=cake_swap[step++]; pos>=1; --pos){

仅仅调整了搜索顺序，调用搜索函数次数由29次降到11次（对应的翻转方法：9，6，9，6，9，6），求第1个烙饼数到第10个烙饼数，所用的总时间也由原来的38秒降到21秒。）

四，源码及分析

#include <iostream>
#include <cassert>
#include <cstdio>
class laobing
{
private:
     int *m_CakeArray;	// 烙饼信息数组
     int  m_nCakeCnt;	// 烙饼个数
     int  m_nMaxSwap;	// 最多交换次数。根据前面的推断，这里最多为
                        // m_nCakeCnt * 2 
     int *m_SwapArray;	// 交换结果数组

     int *m_ReverseCakeArray;	// 当前翻转烙饼信息数组
     int *m_ReverseCakeArraySwap;	// 当前翻转烙饼交换结果数组
     int  m_nSearch;	// 当前搜索次数信息
     
public:
    laobing()    
     {
          m_nCakeCnt = 0;
          m_nMaxSwap = 0;
     }
    ~laobing()
    {
          if(m_CakeArray != NULL)
               delete m_CakeArray;
          
          if( m_SwapArray != NULL ) 
               delete m_SwapArray;
          
          if( m_ReverseCakeArray != NULL )         
               delete m_ReverseCakeArray; 
          
          if( m_ReverseCakeArraySwap != NULL )      
               delete m_ReverseCakeArraySwap;
          
    }
   
     //
     // 计算烙饼翻转信息
     // @param
     // pCakeArray	存储烙饼索引数组
     // nCakeCnt	烙饼个数
     //
     void Run(int* pCakeArray, int nCakeCnt)
     {
          Init(pCakeArray, nCakeCnt);
          m_nSearch = 0;
          Search(0);
     }

     void mOutput(int* CakeArray, int nCakeCnt,int *m_SwapArray,int m_nMaxSwap)
     {
         int t; 
         for(int i = 0; i < m_nMaxSwap; i++)//swap times
          {
                for(int j1 = 0,j2=m_SwapArray[i]; j1<j2; j1++,j2--) //reverse array
                {
                     t = CakeArray[j1]; 
                     CakeArray[j1] = CakeArray[j2];
                     CakeArray[j2] = t;
                 }
               
               for(int k=0;k<nCakeCnt;++k)
                   printf("%d ", CakeArray[k]);
               printf("\n");
               
          }
     }
     void Output()// 输出烙饼具体翻转的次数
     {
          for(int i = 0; i < m_nMaxSwap; i++)
          {
               printf("%d ", m_SwapArray[i]);
          }
          
		
          printf("\n|Search Times| : %d\n", m_nSearch);
          printf("Total Swap times = %d\n", m_nMaxSwap);
          
          mOutput(m_CakeArray, m_nCakeCnt,m_SwapArray,m_nMaxSwap);//输出交换过程
     }

private:

     //
     // 初始化数组信息
     // @param
     // pCakeArray	存储烙饼索引数组
     // nCakeCnt	烙饼个数
     //
     void Init(int* pCakeArray, int nCakeCnt)
     {
          assert(pCakeArray != NULL);
          assert(nCakeCnt > 0);

          m_nCakeCnt = nCakeCnt;

          // 初始化烙饼数组
          m_CakeArray = new int[m_nCakeCnt]; 
          assert(m_CakeArray != NULL);
          for(int i = 0; i < m_nCakeCnt; i++)
          {
               m_CakeArray[i] = pCakeArray[i];
          }

          // 设置最多交换次数信息
          m_nMaxSwap = UpBound(m_nCakeCnt);

          // 初始化交换结果数组 
          m_SwapArray = new int[m_nMaxSwap + 1];
          assert(m_SwapArray != NULL);

          // 初始化中间交换结果信息
          m_ReverseCakeArray = new int[m_nCakeCnt];
          for(int i = 0; i < m_nCakeCnt; i++)
          {
               m_ReverseCakeArray[i] = m_CakeArray[i];
          }
          m_ReverseCakeArraySwap = new int[m_nMaxSwap];
     }
    
    
     int UpBound(int nCakeCnt)// 寻找当前翻转的上界
     {
          return nCakeCnt*2;
     }

     int LowerBound(int* pCakeArray, int nCakeCnt) // 寻找当前翻转的下界
     {
          int t, ret = 0;

          // 根据当前数组的排序信息情况来判断最少需要交换多少次
          for(int i = 1; i < nCakeCnt; i++)
          {
               // 判断位置相邻的两个烙饼，是否为尺寸排序上相邻的
               t = pCakeArray[i] - pCakeArray[i-1];
               if((t == 1) || (t == -1))
               {
               } 
               else
               {
                    ret++;
               }
          }
          return ret;
     }

     // 排序的主函数
     void Search(int step)
     {
          int i, nEstimate;

          m_nSearch++;

          // 估算这次搜索所需要的最小交换次数
          nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
          if(step + nEstimate > m_nMaxSwap)
               return;

          // 如果已经排好序，即翻转完成，输出结果
          if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
          {
               if(step < m_nMaxSwap)
               { 
                    m_nMaxSwap = step;
                    for(i = 0; i < m_nMaxSwap; i++)
                         m_SwapArray[i] = m_ReverseCakeArraySwap[i];
               }
               return;
          }

          // 递归进行翻转
          for(i = 1; i < m_nCakeCnt; i++)
          {
               Revert(0, i);//反转
               m_ReverseCakeArraySwap[step] = i; //第一步 反转的哪一个
               Search(step + 1);
               Revert(0, i);
          }
     }
     //
     // true : 已经排好序
     // false : 未排序
     //
     bool IsSorted(int* pCakeArray, int nCakeCnt)
     {
          for(int i = 1; i < nCakeCnt; i++)
          {
               if(pCakeArray[i-1] > pCakeArray[i])
               {
                    return false;
               }
          }
          return true;
     }

     //
     // 翻转烙饼信息
     //    
     void Revert(int nBegin, int nEnd)
     {
          assert(nEnd > nBegin);
          int i, j, t;

          // 翻转烙饼信息
          for(i = nBegin, j = nEnd; i < j; i++, j--)
          {
               t = m_ReverseCakeArray[i]; 
               m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
               m_ReverseCakeArray[j] = t;
          }
     }


};

int main()
{
    
    laobing ll;//这里ll 不可以加括号
    laobing *l=new laobing();
    int aa[10]={ 3,2,1,6,5,4,9,8,7,0};
    
    l->Run(aa,10);
    l->Output();
    
    ll.Run(aa,10);
    return 0;
}

输出结果：

4 8 6 8 4 9
|Search Times| : 172126
Total Swap times = 6
5 6 1 2 3 4 9 8 7 0
7 8 9 4 3 2 1 6 5 0
1 2 3 4 9 8 7 6 5 0
5 6 7 8 9 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9

五，优化：

在网上下了《编程之美》“第6刷”的源代码，结果在编译时存在以下问题：

1） Assert 应该是 assert

2） m_arrSwap 未被定义，应该改为m_SwapArray

3 ）Init函数两个for循环，后一个没定义变量i，应该将i 改为 int i

另外，每运行一次Run函数，就会调用Init函数，就会申请新的内存，但却没有释放原来的内存，会造成内存泄漏。if(step + nEstimate > m_nMaxSwap) 这句还会造成后面对m_ReverseCakeArraySwap数组的越界访问，使程序不能正常运行。

书上程序的低效主要是由于进行剪枝判断时，没有考虑好边界条件，可进行如下修改：

1 ） if(step + nEstimate > m_nMaxSwap) >改为 >=。

2 ） 判断下界时，如果最大的烙饼不在最后一个位置，则要多翻转一次，因而在LowerBound函数return ret; 前插入行：

if (pCakeArray[nCakeCnt-1] != nCakeCnt-1)

ret++;

3 ） n个烙饼，翻转最大的n-2烙饼最多需要2*(n-2)次，剩下的2个最多1次，因而上限值为2*n-3，因此，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，这样每步与m_nMaxSwap的判断就可以取大等于号。

4 ）采用书上提到的确定“上限值”的方法，直接构建一个初始解，取其翻转次数为m_nMaxSwap的初始值。

1和2任改一处，都能使搜索次数从172126降到两万多，两处都改，搜索次数降到3475。若再改动第3处，搜索次数降到2989；若采用4的方法（此时初始值为10），搜索次数可降到1045。

六，思考

书中P22页提到动态规划，但最后却给出了解决最优化问题普遍适用但效率可能是最差的递归方法。这不禁让人疑惑：这也不美啊！？如果我们能证明该问题满足动态规划或贪心算法的使用条件，解决问题的时间复杂度将会降到多项式时间甚至N^2。但书中提到动态规划却最终没有使用，又没有讲明原因，我觉得是一种疏失（应该不算错误）。那我们就来想一下为什么没有动态规划或贪心算法的原因。

我们知道动态规划方法是一种自底向上的获取问题最优解的方法，它采用子问题的最优解来构造全局最优解。利用动态规划求解的问题需要满足两个条件：即（1）最优子结构 （2）子结构具有重叠性。条件（1）使我们可以利用子问题的最优解来构造全局最优解，而条件（2）是我们在计算过程中可以利用子结构的重叠性来减少运算次数。此外，《算法导论》上还以有向图的无权最短路径和无权最长路径为例提出条件（3）子问题必须独立。

首先我们假定烙饼问题存在优化子结构。假如我们有N个烙饼，把他们以其半径由小到大进行编号。优化子结构告诉我们对于i个烙饼，我们只需要先排列前(i-1)个，然后再将第i个归位；或先排列第2到i个，最后将第一个归位；又或是找到一个位置k[i<=k<j]像矩阵乘法加括号那样，使得我们先排列前k个，再排列后j-k个，最后再将二者合并，以找到一个最佳翻转策略等等...

根据动态规划算法的计算过程，我们需要一个N*N矩阵M，其中M[i][j]表示将编号i至编号j的烙饼排序所需要的翻转次数。但我们真的能从M[0][0..j-1]和M[1][j+1]，或与M[i][j]同行同列的值来计算M[i][j]吗？如果能，我们就能获得多项式时间的算法。

我们来看书中给出的例子：(顶端)3，2，1，6，5，4，9，8，7，0(底端)，我们最终的目标是计算M[0][9]。
这里我们以计算M[0][4]为例，计算的矩阵我已经在下面给出：
0 1 2 3 4 5 6 7 8 9
------------------------
0|0 1 (1){1}[？]
1| 0 1 (1){1}
2| 0 1 (1)
3| 0 0
4| 0
------------------

实际上如果我们要向将0-4号烙饼(注意：烙饼编号也等同于其半径)排为正序(中间有其他烙饼也没关系)，按照程序给出的结果， 我们需要进行3次翻转，分别为[2,5,9](即分别翻转队列中第二(从零开始)、五、九个烙饼，这里的数字不是烙饼的编号)：
[1] [2] [3] 6 5 [4] 9 8 7 [0]
[4] 5 6 [3] [2] [1] 9 8 7 [0]
[0] 7 8 9 [1] [2] [3] 6 5 [4]

我们知道，该矩阵中每一个数的背后都隐含着一个烙饼的排列，例如M[0][4]就应该对应0,7,8,9,1,2,3,6,5,4
所以，每一个M[i][j]的选取都蕴含着其子排列的顺序的变化。
计算M[i][j]的时候，我们需要计算i-j号饼的全部划分(不包括全部为1的划分)所能构成的翻转结构，并取其翻转 次数最少的哪一个最为M[i][j]的最终值。例如，我们在计算M[0][4]的时候，需要查看：

/**先将0和1-4号分别排序，最后将二者合并为有序所需要的翻转次数*/
M[0][0],M[1][4]

/** 同上 */
M[0][1],M[2][4]

/** 同上 */
M[0][2],M[3][4]

/** 同上 */
M[0][3],M[4][4]

/* 先将0、1、2、3-4号分别排序，最后将4者合并为有序所需要的翻转次数.
* 注意这里又包含将4个分组再次进行划分的问题！
*/
M[0][0],M[1][1],M[2][2],M[3][4]
.....//中间略
M[0][3],M[4][4]

如果再加上运算过程中我们可以淘汰超过最大反转次数的方案（剪枝？），我们完成全部的运算所经历的运算过程的时间复杂度已经不是多项式时间的，而是和先前所说的递归方法已没什么两样。

造成这种现象的原因是：某个子问题的最优解不一定是整体的最优解，所以我们在处理整个问题的时候，需要遍历所有可能的子问题，并计算它到整体问题所消耗的代价，才能最终作出有利于整体问题的选择。

所以我们一开始的假设，即烙饼问题有优化子结构的假设是错误的。因此我们不能用动态规划，同理也不能用贪心算法。

但说到每一步的“选择”问题，我记得算法导论上有一个叫做“A*”的算法，它的思想是在进行每一步选择的时候都“推算”最终可能需要的代价，并选择当前代价最小的分支进行遍历。这个“推算”的结果可能不会是最终的代价，而只是作为分支选择的依据。如果谁有兴趣就做一下吧 :-)