《程式設計之美》讀書筆記02： 1.3 一摞烙餅的排序

《程式設計之美》讀書筆記02： 1.3 一摞烙餅的排序

問題：

    星期五的晚上，一幫同僚在希格瑪大廈附近的“硬碟酒吧”多喝了幾杯。程式員多喝了幾杯之後談什麼呢？自然是算法問題。有個同僚說：“我以前在餐館打工，顧客經常點非常多的烙餅。店裡的餅大小不一，我習慣在到達顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一隻手托着盤子，隻好用另一隻手，一次抓住最上面的幾塊餅，把它們上下颠倒個個兒，反複幾次之後，這摞烙餅就排好序了。我後來想，這實際上是個有趣的排序問題：假設有n塊大小不一的烙餅，那最少要翻幾次，才能達到最後大小有序的結果呢？”

你能否寫出一個程式，對于n塊大小不一的烙餅，輸出最優化的翻餅過程呢？

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秒。）

最終代碼：

//1.3_pancake_f.cpp by flyingheart ＃ qq.com

#include<iostream>

#include<fstream>

#include<vector>

#include<algorithm>

#include<ctime>

using namespace std;

class Pancake{

public:

Pancake() {}

void print() const;

void process(); //顯示最優解的翻轉過程

int run(const int cake_arr[], int size, bool show=true);

void calc_range(int na, int nb);

private:

Pancake(const Pancake&);

Pancake& operator=(const Pancake&);

inline bool init(const int cake_arr[], int& size);

void search_cake(int size, int step, int least_swap_old);

void reverse_cake(int index) { //翻轉0到index間的烙餅

++count_reverse;

std::reverse(&cake[0], &cake[index + 1]);

}

bool next_search_cake(int pos, int size, int step, int least_swap)

{

if (least_swap + step >= get_min_swap()) return true;

cake_swap[step] = pos;

reverse_cake(pos);

search_cake(size,step,least_swap);

reverse_cake(pos);

return false;

}

int get_min_swap() const { return result.size();}

void output(int i, const std::string& sep, int width) const {

cout.width(width);

cout << i << sep;

}

void output(const std::string& sep, int width) const {

cout.width(width);

cout << sep;

}

vector<int> cake_old; //要處理的原烙餅數組

vector<int> cake; //目前各個烙餅的狀态

vector<int> result; //最優解中，每次翻轉的烙餅位置

vector<int> cake_swap; //每次翻轉的烙餅位置

vector<int> cake_order; //第step+1次翻轉時，翻轉位置的優先順序

int min_swap_init; //最優解的翻轉次數初始值

int count_search; //search_cake被調用次數

int count_reverse; //reverse_cake被調用次數

};

void Pancake::print() const

{

int min_swap = get_min_swap();

if (min_swap == 0) return;

cout << "minimal_swap initial: " << min_swap_init

<< " final: "<< min_swap

<< "/nsearch/reverse function was called: " << count_search

<< "/" << count_reverse << " times/nsolution: ";

for (int i = 0; i < min_swap; ++i) cout << result[i] << " ";

cout<< "/n/n";

}

void Pancake::process()

{

int min_swap = get_min_swap();

if (min_swap == 0) return;

cake.assign(cake_old.begin(), cake_old.end());

int cake_size = cake_old.size();

const int width = 3, width2 = 2 * width + 3;

output("No.", width2);

for (int j = 0; j < cake_size; ++j) output(j," ",width);

cout << "/n";

output("old:", width2);

for (int j = 0; j < cake_size; ++j) output(cake[j]," ",width);

cout << "/n";

for (int i = 0; i < min_swap; ++i){

reverse_cake(result[i]);

output(i + 1," ",width);

output(result[i],": ",width);

for (int j = 0; j < cake_size; ++j) output(cake[j]," ",width);

cout << "/n";

}

cout << "/n/n";

}

bool Pancake::init(const int cake_arr[], int& size)

{

result.clear();

if (cake_arr == NULL) return false;

cake_swap.resize(size * 2);

cake_order.resize(size * size * 2);

count_search = 0;

count_reverse = 0;

cake_old.assign(cake_arr,cake_arr + size);

//去除末尾已就位的烙餅，修正烙餅數組大小。

while (size > 1 && size - 1 == cake_arr[size - 1]) --size;

if (size <= 1) return false;

cake.assign(cake_arr,cake_arr + size);

for (int j = size - 1; ;) { //計算一個解作為min_swap初始值。

while(j > 0 && j == cake[j]) --j;

if (j <= 0) break;

int i = j;

while (i >= 0 && cake[i] != j) --i;

if (i != 0) {

reverse_cake(i);

result.push_back(i);

}

reverse_cake(j);

result.push_back(j);

--j;

}

cake.assign(cake_arr,cake_arr + size); //恢複原來的數組

cake.push_back(size); //多放一個烙餅，避免後面的邊界判斷

cake_swap[0] = 0; //假設第0步翻轉的烙餅編号為0

min_swap_init= get_min_swap();

return true;

}

int Pancake::run(const int cake_arr[], int size, bool show)

{

if (! init(cake_arr, size)) return 0;

int least_swap = 0;

//size = cake.size() - 1;

for (int i = 0; i < size; ++i)

if (cake[i] - cake[i + 1] + 1u > 2) ++least_swap;

if (get_min_swap() != least_swap) search_cake(size, 0, least_swap);

if (show) print();

return get_min_swap();

}

void Pancake::search_cake(int size, int step, int least_swap_old)

{

++count_search;

while (size > 1 && size - 1 == (int)cake[size - 1]) --size; //去除末尾已就位的烙餅

int *first = &cake_order[step * cake.size()];

int *last = first + size;

int *low = first, *high = first + size;

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

if (pos == last_swap) continue;

int least_swap = least_swap_old ;

if (cake[pos] - cake[pos + 1] + 1u <= 2) ++least_swap;

if (cake[0] - cake[pos + 1] + 1u <= 2) --least_swap;

if (least_swap + step >= get_min_swap()) continue;

if (least_swap == 0) {

cake_swap[step] = pos;

result.assign(&cake_swap[1], &cake_swap[step + 1]);

return;

}

//根據least_swap值大小，分别儲存pos值，并先處理使least_swap_old減小1的翻轉

if (least_swap == least_swap_old) *low++ =pos;

else if (least_swap > least_swap_old) *--high =pos;

else next_search_cake(pos, size, step, least_swap);

}

//再處理使least_swap_old不變的翻轉

for(int *p = first; p < low; p++)

if (next_search_cake(*p, size, step, least_swap_old)) return;

//最後處理使least_swap_old增加1的翻轉

for(int *p = high; p < last; p++)

if (next_search_cake(*p, size, step, least_swap_old + 1)) return;

}

void Pancake::calc_range(int na, int nb)

{

if (na > nb || na <= 0) return;

clock_t ta = clock();

static std::vector<int> arr;

arr.resize(nb);

unsigned long long total_search = 0;

unsigned long long total_reverse = 0;

for (int j = na; j <= nb; ++j) {

for (int i = 0; i < j; ++i) arr[i] = i;

int max = 0;

unsigned long long count_s = 0;

unsigned long long count_r = 0;

clock_t tb = clock();

while (std::next_permutation(&arr[0], &arr[j])) {

int tmp = run(&arr[0],j,0);

if (tmp > max) max = tmp;

count_s += count_search;

count_r += count_reverse;

}

total_search += count_s;

total_reverse += count_r;

output(j, " ",2);

output(max," time: ",3);

output(clock() - tb," ms ",8);

cout << " search/reverse: " << count_s << "/" << count_r << "/n";

}

cout << " total search/reverse: " << total_search

<< "/" << total_reverse << "/n"

<< "time : " << clock() - ta << " ms/n";

}

int main()

{

int aa[10]={ 3,2,1,6,5,4,9,8,7,0};

//int ab[10]={ 4,8,3,1,5,2,9,6,7,0};

// int ac[]={1,0, 4, 3, 2};

Pancake cake;

cake.run(aa,10);

cake.process();

//cake.run(ab,10);

//cake.process();

//cake.run(ac,sizeof(ac)/sizeof(ac[0]));

//cake.process();

cake.calc_range(1,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。