雁過(guò)無(wú)痕

《編程之美》讀書筆記：1.3 一摞烙餅的排序

問(wèn)題：

    星期五的晚上，一幫同事在希格瑪大廈附近的“硬盤酒吧”多喝了幾杯。程序員多喝了幾杯之后談什么呢？自然是算法問(wèn)題。有個(gè)同事說(shuō)：“我以前在餐館打工，顧客經(jīng)常點(diǎn)非常多的烙餅。店里的餅大小不一，我習(xí)慣在到達(dá)顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一只手托著盤子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個(gè)個(gè)兒，反復(fù)幾次之后，這摞烙餅就排好序了。我后來(lái)想，這實(shí)際上是個(gè)有趣的排序問(wèn)題：假設(shè)有n塊大小不一的烙餅，那最少要翻幾次，才能達(dá)到最后大小有序的結(jié)果呢？”

你能否寫出一個(gè)程序，對(duì)于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過(guò)程呢？

n個(gè)烙餅經(jīng)過(guò)翻轉(zhuǎn)后的所有狀態(tài)可組成一棵樹(shù)。尋找翻轉(zhuǎn)最少次數(shù)，相當(dāng)于在樹(shù)中搜索層次最低的某個(gè)節(jié)點(diǎn)。

由于每層的節(jié)點(diǎn)數(shù)呈幾何數(shù)量級(jí)增長(zhǎng)，在n較大時(shí)，使用廣度優(yōu)先遍歷樹(shù)，可能沒(méi)有足夠的內(nèi)存來(lái)保存中間結(jié)果（考慮到每層的兩個(gè)節(jié)點(diǎn)，可以通過(guò)旋轉(zhuǎn)，移位等操作互相轉(zhuǎn)換，也許每層的狀態(tài)可以用一個(gè)函數(shù)來(lái)生成，這時(shí)可以采用廣度優(yōu)先方法。），因而采用深度優(yōu)先。但這棵樹(shù)是無(wú)限深的，必須限定搜索的深度（即最少翻轉(zhuǎn)次數(shù)的上限值），當(dāng)深度達(dá)到該值時(shí)不再繼續(xù)往下搜索。最少翻轉(zhuǎn)次數(shù)，必然小等于任何一種翻轉(zhuǎn)方案所需的翻轉(zhuǎn)次數(shù)，因而只要構(gòu)造出一種方案，取其翻轉(zhuǎn)次數(shù)即可做為其初始值。最簡(jiǎn)單的翻轉(zhuǎn)方案就是：對(duì)最大的未就位的烙餅，將其翻轉(zhuǎn)，再找到最終結(jié)果中其所在的位置，翻轉(zhuǎn)一次使其就位。因此，對(duì)編號(hào)在n-1和2之間的烙餅，最多翻轉(zhuǎn)了2*(n-2)次，剩下0和1號(hào)烙餅最多翻轉(zhuǎn)1次，因而最少翻轉(zhuǎn)次數(shù)的上限值是：2*(n-2)+1=2*n-3（從網(wǎng)上可搜索到對(duì)該上限值最新研究結(jié)果：上限值為18/11*n），當(dāng)然，最好還是直接計(jì)算出采用這種方案的翻轉(zhuǎn)次數(shù)做為初始值。

減少遍歷次數(shù)：

1 減小“最少翻轉(zhuǎn)次數(shù)上限值”的初始值，采用前面提到的翻轉(zhuǎn)方案，取其翻轉(zhuǎn)次數(shù)為初始值。對(duì)書中的例子{3,2,1,6,5,4,9,8,7,0}，初始值可以取10。

2 避免出現(xiàn)已處理過(guò)的狀態(tài)一定會(huì)減少遍歷嗎？答案是否定的，深度優(yōu)先遍歷，必須遍歷完一個(gè)子樹(shù)，才能遍歷下一個(gè)子樹(shù)，如果一個(gè)解在某層比較靠后位置，若不允許處理已出現(xiàn)過(guò)的狀態(tài)時(shí)，可能要經(jīng)過(guò)很多次搜索，才能找到這個(gè)解，但允許處理已出現(xiàn)過(guò)的狀態(tài)時(shí)，可能會(huì)很快找到這個(gè)解，并減小“最少翻轉(zhuǎn)次數(shù)的上限值”，使更多的分支能被剪掉，從而減少遍歷。比如說(shuō)，兩個(gè)子樹(shù)A、B，搜索子樹(shù)A，100次后可得到一個(gè)解對(duì)應(yīng)翻轉(zhuǎn)次數(shù)20，搜索子樹(shù)B，20次后可得到翻轉(zhuǎn)次數(shù)為10的解，不允許處理已出現(xiàn)過(guò)的狀態(tài)，就會(huì)花100次遍歷完子樹(shù)A后，才開(kāi)始遍歷B，但允許翻轉(zhuǎn)回上一次狀態(tài)，搜索會(huì)在A、B間交叉進(jìn)行，就可能只要70次找到子樹(shù)B的那個(gè)解（翻轉(zhuǎn)次數(shù)為10+2=12），此時(shí)，翻轉(zhuǎn)次數(shù)比較少，能減少更多的搜索，搜索次數(shù)明顯減少。以書中的{3,2,1,6,5,4,9,8,7,0}為例，按程序（1.3_pancake.cpp），不允許翻轉(zhuǎn)回上次狀態(tài)時(shí)需搜索195次，而允許翻轉(zhuǎn)回上次狀態(tài)時(shí)只要搜索116次。

3 如果最后的幾個(gè)烙餅已經(jīng)就位，只須考慮前面的幾個(gè)烙餅。對(duì)狀態(tài)(0,1,3,4,2,5,6)，編號(hào)為5和6的烙餅已經(jīng)就位，只須考慮前5個(gè)烙餅，即狀態(tài)(0,1,3,4,2)。如果一個(gè)最優(yōu)解，從某次翻轉(zhuǎn)開(kāi)始移動(dòng)了一個(gè)已經(jīng)就位的烙餅，且該烙餅后的所有烙餅都已經(jīng)就位，那么，對(duì)這個(gè)解法，從這次翻轉(zhuǎn)開(kāi)始得到的一系列狀態(tài)，從中移除這個(gè)烙餅，得到新的狀態(tài)，可以設(shè)計(jì)出一個(gè)新的解法對(duì)應(yīng)這系列新的狀態(tài)。該解法所用的翻轉(zhuǎn)次數(shù)不會(huì)比原來(lái)的多。

4 估計(jì)每個(gè)狀態(tài)還需要翻轉(zhuǎn)的最少次數(shù)（即下限值），加上當(dāng)前的深度，如果大等于上限值，就無(wú)需繼續(xù)遍歷。這個(gè)下限值可以這樣確定：從最后一個(gè)位置開(kāi)始，往前找到第一個(gè)與最終結(jié)果位置不同的烙餅編號(hào)（也就是說(shuō)排除最后幾個(gè)已經(jīng)就位的烙餅），從該位置到第一個(gè)位置，計(jì)算相鄰的烙餅的編號(hào)不連續(xù)的次數(shù)，再加上1。每次翻轉(zhuǎn)最多只能使不連續(xù)的次數(shù)減少1，但很多人會(huì)忽略掉這個(gè)情況：最大的烙餅沒(méi)有就位時(shí)，必然需要一次翻轉(zhuǎn)使其就位，而這次翻轉(zhuǎn)卻不改變不連續(xù)次數(shù)。（可以在最后面增加一個(gè)更大的烙餅，使這次翻轉(zhuǎn)可以改變不連續(xù)數(shù)。）如：對(duì)狀態(tài)(0,1,3,4,2,5,6)等同于狀態(tài)(0,1,3,4,2)，由于1、3和4、2不連續(xù)，因而下限值為2+1=3。下限值也可以這樣確定：在最后面增加一個(gè)已經(jīng)已就位的最大的烙餅，然后再計(jì)算不連續(xù)數(shù)。如：(0,1,3,4,2)，可以看作(0,1,3,4,2,5)，1和3 、4和2 、2和5這三個(gè)不連續(xù)，下限值為3。

5多數(shù)情況下，翻轉(zhuǎn)次數(shù)的上限值越大，搜索次數(shù)就越多。可以采用貪心算法，通過(guò)調(diào)整每次所有可能翻轉(zhuǎn)的優(yōu)先順序，盡快找到一個(gè)解，從而減少搜索次數(shù)。比如，優(yōu)先搜索使“下限值”減少的翻轉(zhuǎn)，其次是使“下限值”不變的翻轉(zhuǎn)，最后才搜索使“下限值”增加的翻轉(zhuǎn)。對(duì)“下限值”不變的翻轉(zhuǎn)，還可以根據(jù)其下次的翻轉(zhuǎn)對(duì)“下限值”的影響，再重新排序。由于進(jìn)行了優(yōu)先排序，翻轉(zhuǎn)回上一次狀態(tài)能減少搜索次數(shù)的可能性得到進(jìn)一步降低。

6 其它剪枝方法：

假設(shè)第m次翻轉(zhuǎn)時(shí)，“上限值”為min_swap。

如果在某個(gè)位置的翻轉(zhuǎn)得到一個(gè)解（即翻轉(zhuǎn)次數(shù)為m），則其它位置可以不搜索（因?yàn)樵谄渌恢玫姆D(zhuǎn)，能得到的最少翻轉(zhuǎn)次數(shù)必然大等m）。

如果在某個(gè)位置的翻轉(zhuǎn)后，“下限值”為k，并且 k+m>=min_swap，則對(duì)所有的使新“下限值”kk大等于k的翻轉(zhuǎn)，都有 kk+m>=min_swap，因而都可以不搜索。

另外，由于翻轉(zhuǎn)時(shí)，只有兩個(gè)位置的改變才對(duì)“下限值”有影響，因而可以記錄每個(gè)狀態(tài)的“下限值”，翻轉(zhuǎn)時(shí)，通過(guò)幾次比較，就可以確定新?tīng)顟B(tài)的“下限值”。（判斷不連續(xù)次數(shù)時(shí)，最好寫成 -1<=x && x<=1， 而不是x==1 || x==-1。對(duì)于 int x; a<=x && x<=b，編譯器可以將其優(yōu)化為 unsigned (x-a) <= b-a。）

結(jié)果：

對(duì)書上的例子{3,2,1,6,5,4,9,8,7,0}：

（這個(gè)例子比較特殊，代碼1.3_pancake_2.cpp（與1.3_pancake_1.cpp的最主要區(qū)別在于，增加了對(duì)翻轉(zhuǎn)優(yōu)先順序的判斷，代碼下載），在不允許翻轉(zhuǎn)回上次狀態(tài)、取min_swap的初始值為2*10-2=18時(shí)，調(diào)用搜索函數(shù)29次，翻轉(zhuǎn)函數(shù)56次）。

　　另外，對(duì)1.3_pancake_2.cpp的第148行做個(gè)簡(jiǎn)單的改動(dòng)：
        for (int pos=1, last_swap=cake_swap[step++]; pos<size; ++pos){  
       改為：
        for (int pos=size-1, last_swap=cake_swap[step++]; pos>0; ++pos){

        只是改變了搜索順序，但卻極大提升了搜索效率。對(duì)書上的例子，搜索次數(shù)進(jìn)一步降到11次（實(shí)際上前六次搜索找到了一個(gè)解，后而的幾次用于判斷這個(gè)解是是最優(yōu)解）。遍歷所有可能的排列求第1個(gè)……第10個(gè)烙餅數(shù)所用的總時(shí)間，也由原來(lái)的38秒降到21秒。

1.3_pancake_f
  1//1.3_pancake_f.cpp   by  flyingheart ＃ qq.com
  2#include<iostream>
  3#include<fstream>
  4#include<vector>
  5#include<algorithm>
  6#include<ctime>
  7using namespace std;
  8
  9class Pancake{
 10 public:
 11  Pancake() {}
 12  void print() const;
 13  void process();               //顯示最優(yōu)解的翻轉(zhuǎn)過(guò)程
 14  int run(const int cake_arr[], int size, bool show=true);
 15  void calc_range(int na, int nb);
 16
 17 private: 
 18  Pancake(const Pancake&);
 19  Pancake& operator=(const Pancake&);
 20  inline bool init(const int cake_arr[], int& size);
 21  void search_cake(int size, int step, int least_swap_old);
 22  void reverse_cake(int index) { //翻轉(zhuǎn)0到index間的烙餅
 23    ++count_reverse; 
 24    std::reverse(&cake[0], &cake[index + 1]);
 25  }
 26  
 27  bool next_search_cake(int pos, int size, int step, int least_swap)
 28  {
 29    if (least_swap + step >= get_min_swap()) return true;
 30    cake_swap[step] = pos;
 31    reverse_cake(pos);
 32    search_cake(size,step,least_swap);
 33    reverse_cake(pos);
 34    return false;
 35  }
 36  
 37  int get_min_swap() const { return result.size();}
 38  
 39  void output(int i, const std::string& sep, int width) const {
 40    cout.width(width);
 41    cout << i << sep;
 42  }
 43  
 44  void output(const std::string& sep, int width) const {
 45    cout.width(width);
 46    cout << sep;
 47  }
 48  
 49  vector<int> cake_old;        //要處理的原烙餅數(shù)組
 50  vector<int> cake;            //當(dāng)前各個(gè)烙餅的狀態(tài)
 51  vector<int> result;          //最優(yōu)解中，每次翻轉(zhuǎn)的烙餅位置
 52  vector<int> cake_swap;       //每次翻轉(zhuǎn)的烙餅位置
 53  vector<int> cake_order;      //第step+1次翻轉(zhuǎn)時(shí)，翻轉(zhuǎn)位置的優(yōu)先順序
 54  int min_swap_init;           //最優(yōu)解的翻轉(zhuǎn)次數(shù)初始值
 55  int count_search;            //search_cake被調(diào)用次數(shù)
 56  int count_reverse;           //reverse_cake被調(diào)用次數(shù)
 57};
 58
 59
 60void Pancake::print() const
 61{
 62  int min_swap = get_min_swap();
 63  if (min_swap == 0) return; 
 64  cout << "minimal_swap initial: " << min_swap_init 
 65       << "  final: "<< min_swap 
 66       << "\nsearch/reverse function was called: " << count_search
 67       << "/" << count_reverse << " times\nsolution: ";
 68  for (int i = 0; i < min_swap; ++i) cout << result[i] << " ";
 69  cout<< "\n\n";
 70}
 71
 72void Pancake::process()
 73{
 74  int min_swap = get_min_swap(); 
 75  if (min_swap == 0) return;
 76  cake.assign(cake_old.begin(), cake_old.end());
 77  int cake_size = cake_old.size();
 78  const int width = 3, width2 = 2 * width + 3;
 79  output("No.", width2);
 80  for (int j = 0; j < cake_size; ++j) output(j," ",width);   
 81  cout << "\n";     
 82  output("old:", width2);    
 83  
 84  for (int j = 0; j < cake_size; ++j) output(cake[j]," ",width);  
 85  cout << "\n";        
 86  
 87  for (int i = 0; i < min_swap; ++i){
 88    reverse_cake(result[i]);
 89    output(i + 1," ",width);  
 90    output(result[i],": ",width);  
 91    for (int j = 0; j < cake_size; ++j)  output(cake[j]," ",width);  
 92    cout << "\n";
 93  }
 94  cout << "\n\n";
 95}
 96
 97bool Pancake::init(const int cake_arr[], int& size)
 98{
 99  result.clear();
100  if (cake_arr == NULL) return false;
101  cake_swap.resize(size * 2);
102  cake_order.resize(size * size * 2);
103  count_search = 0;
104  count_reverse = 0;
105  cake_old.assign(cake_arr,cake_arr + size);
106  //去除末尾已就位的烙餅，修正烙餅數(shù)組大小。
107  while (size > 1 && size - 1 == cake_arr[size - 1]) --size; 
108  if (size <= 1) return false;
109  
110  cake.assign(cake_arr,cake_arr + size);
111  for (int j = size - 1; ;) {           //計(jì)算一個(gè)解作為min_swap初始值。
112    while(j > 0 && j == cake[j]) --j;
113    if (j <= 0) break;
114    int i = j;
115    while (i >= 0 && cake[i] != j) --i;
116    if (i != 0) {
117      reverse_cake(i);
118      result.push_back(i);
119    }
120    reverse_cake(j);
121    result.push_back(j);
122    --j;
123  }
124  cake.assign(cake_arr,cake_arr + size); //恢復(fù)原來(lái)的數(shù)組
125  cake.push_back(size);                 //多放一個(gè)烙餅，避免后面的邊界判斷
126  cake_swap[0] = 0;                     //假設(shè)第0步翻轉(zhuǎn)的烙餅編號(hào)為0
127  min_swap_init= get_min_swap();
128  return true;
129}
130
131int Pancake::run(const int cake_arr[], int size, bool show)
132{
133  if (! init(cake_arr, size)) return 0;
134  int least_swap = 0;
135  //size = cake.size() - 1;
136  for (int i = 0; i < size; ++i)
137    if (cake[i] - cake[i + 1] + 1u > 2) ++least_swap;  
138  if (get_min_swap() != least_swap) search_cake(size, 0, least_swap);
139  if (show) print();
140  return get_min_swap();
141}
142
143void Pancake::search_cake(int size, int step, int least_swap_old)
144{
145  ++count_search;
146  while (size > 1 && size - 1 == (int)cake[size - 1]) --size; //去除末尾已就位的烙餅
147  int *first = &cake_order[step * cake.size()];
148  int *last = first + size;
149  int *low = first, *high = first + size;
150
151  for (int pos = size - 1, last_swap = cake_swap[step++]; pos > 0; --pos){
152    if (pos == last_swap) continue;
153    int least_swap = least_swap_old ;
154    if (cake[pos] - cake[pos + 1] + 1u <= 2) ++least_swap;
155    if (cake[0] - cake[pos + 1] + 1u <= 2) --least_swap;
156
157    if (least_swap + step >= get_min_swap()) continue;
158    if (least_swap == 0) {
159      cake_swap[step] = pos;
160      result.assign(&cake_swap[1], &cake_swap[step + 1]);
161      return;
162    }
163    
164    //根據(jù)least_swap值大小，分別保存pos值，并先處理使least_swap_old減小1的翻轉(zhuǎn)
165    if (least_swap == least_swap_old) *low++ =pos;
166    else if (least_swap > least_swap_old) *--high =pos;
167    else next_search_cake(pos, size, step, least_swap);   
168  }
169
170  //再處理使least_swap_old不變的翻轉(zhuǎn)
171  for(int *p = first; p < low; p++)
172    if (next_search_cake(*p, size, step, least_swap_old)) return;
173    
174  //最后處理使least_swap_old增加1的翻轉(zhuǎn)
175  for(int *p = high; p < last; p++)
176    if (next_search_cake(*p, size, step, least_swap_old + 1)) return;
177}
178
179void Pancake::calc_range(int na, int nb)
180{
181  if (na > nb || na <= 0) return;
182  clock_t ta = clock();
183  static std::vector<int> arr;
184  arr.resize(nb);
185  unsigned long long total_search = 0;
186  unsigned long long total_reverse = 0;
187  for (int j = na; j <= nb; ++j) {
188    for (int i = 0; i < j; ++i) arr[i] = i;
189    int max = 0;
190    unsigned long long count_s = 0;
191    unsigned long long count_r = 0;
192    clock_t tb = clock();
193    while (std::next_permutation(&arr[0], &arr[j])) {    
194      int tmp = run(&arr[0],j,0);
195      if (tmp > max) max = tmp;
196      count_s += count_search;
197      count_r += count_reverse;
198    }
199    total_search +=  count_s;
200    total_reverse += count_r;
201    output(j, " ",2);
202    output(max,"     time: ",3);
203    output(clock() - tb,"  ms  ",8);
204    cout << " search/reverse: " << count_s << "/" << count_r << "\n";
205  }
206  cout << "  total  search/reverse: " << total_search
207       << "/" << total_reverse << "\n"
208       << "time :  " << clock() - ta << "  ms\n";
209}
210
211int main()
212{
213  int aa[10]={ 3,2,1,6,5,4,9,8,7,0};
214  //int ab[10]={ 4,8,3,1,5,2,9,6,7,0};
215 // int ac[]={1,0, 4, 3, 2};
216  Pancake cake;
217  cake.run(aa,10);
218  cake.process();
219  //cake.run(ab,10);
220  //cake.process(); 
221  //cake.run(ac,sizeof(ac)/sizeof(ac[0]));
222  //cake.process();  
223  cake.calc_range(1,9);
224}
225
226

補(bǔ)充：

在網(wǎng)上下了《編程之美》“第6刷”的源代碼，結(jié)果在編譯時(shí)存在以下問(wèn)題：

1 Assert 應(yīng)該是 assert

2 m_arrSwap 未被定義，應(yīng)該改為m_SwapArray

3 Init函數(shù)兩個(gè)for循環(huán)，后一個(gè)沒(méi)定義變量i，應(yīng)該將i 改為 int i

另外，每運(yùn)行一次Run函數(shù)，就會(huì)調(diào)用Init函數(shù)，就會(huì)申請(qǐng)新的內(nèi)存，但卻沒(méi)有釋放原來(lái)的內(nèi)存，會(huì)造成內(nèi)存泄漏。

書上程序的低效主要是由于進(jìn)行剪枝判斷時(shí)，沒(méi)有考慮好邊界條件，可進(jìn)行如下修改：

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

2  判斷下界時(shí)，如果最大的烙餅不在最后一個(gè)位置，則要多翻轉(zhuǎn)一次，因而在LowerBound函數(shù)return ret; 前插入一行：

if (pCakeArray[nCakeCnt-1] != nCakeCnt-1) ret++; 。

3       n個(gè)烙餅，翻轉(zhuǎn)最大的n-2烙餅最多需要2*(n-2)次，剩下的2個(gè)最多1次，因而上限值為2*n-3，因此，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，這樣每步與m_nMaxSwap的判斷就可以取大等于號(hào)。

4        采用書上提到的確定“上限值”的方法，直接構(gòu)建一個(gè)初始解，取其翻轉(zhuǎn)次數(shù)為m_nMaxSwap的初始值。

1和2任改一處，都能使搜索次數(shù)從172126降到兩萬(wàn)多，兩處都改，搜索次數(shù)降到3475。若再改動(dòng)第3處，搜索次數(shù)降到2989；若采用4的方法（此時(shí)初始值為10），搜索次數(shù)可降到1045。