编程之美(三)一摞烙饼的排序

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

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

1. 最简单的翻转方案

每次翻转找到最大的烙饼将其翻转到最上层，然后翻转到最下层，对于大小前 ( n − 2 ) (n - 2) (n−2)个烙饼，每个只需翻转 2 2 2次即可将其放在排序的位置，而对于最小的两个烙饼来说，我们只需翻转一次即可排序成功，那么对于 n n n个烙饼来说，用这种方式只需 2 ∗ ( n − 2 ) + 1 2 * (n - 2) + 1 2∗(n−2)+1，即 2 n − 3 2n - 3 2n−3次即可将烙饼完全排序

上述的方式自然不是最佳方案，但我们可以将其作为一个上界，即如果我们找到的方案的翻转次数大于 2 n − 3 2n - 3 2n−3，那么肯定不是最佳方案，就可以排除此方案

2. 确定搜索方式

那么我们如何进行搜索呢？ n n n个烙饼经过翻转后的所有状态可组成一棵树。寻找翻转最少次数，相当于在树中搜索层次最低的某个节点。由于每层的节点数呈几何数量级增长，在 n n n较大时，使用广度优先遍历树，可能没有足够的内存来保存中间结果（考虑到每层的两个节点，可以通过旋转，移位等操作互相转换，也许每层的状态可以用一个函数来生成，这时可以采用广度优先方法），因而采用深度优先。而上面我们已经提出了上界，即将该数的范围进行了一个限定，防止无限延伸。

3. 深度优先搜索剪枝策略

(1)在第一个问题中也提到过，我们首先确定了一个上限值，当我们搜索的时候如果当前的搜索次数大于该上限值，那么也就没有搜索下去的必要了
(2)如果在某个位置的翻转之后，"下限值"为 k k k，并且 k + m > = m i n s w a p k + m >= min_swap k+m>=minswap，则对所有的使新"下限值" k k kk kk大于等于 k k k的翻转，都有 k k + m > = m i n s w a p kk + m >= min_swap kk+m>=minswap，因而都可以不搜索(这条对上一条的进一步补充)

4. 确定下限值

对于 n n n个烙饼，依次比较其相邻两个烙饼的大小，如果相差大于 1 1 1的话，说明相邻的两个烙饼不是有序的，那么就最理想的情况而言，其翻转次数需要 + 1 +1 +1，例：烙饼当前顺序为 4 , 3 , 2 , 1 , 5 , 6 {4, 3, 2, 1, 5, 6} 4,3,2,1,5,6，其中 1 1 1与 5 5 5相差大于 1 1 1，那么需要翻转1次(当然这是最理想的情况，也就是最少次数，可以作为我们的下界值)
还可以再精确一点，当当前烙饼序列最后一个元素不为 n − 1 n - 1 n−1，那么翻转次数需要多 + 1 +1 +1次，例：烙饼当前顺序为 6 , 4 , 3 , 2 , 1 , 5 {6, 4, 3, 2, 1, 5} 6,4,3,2,1,5，其中 6 6 6与 4 4 4、 1 1 1与 5 5 5相差大于 1 1 1，那么需要翻转 2 + 1 2 + 1 2+1次

5. 程序编写

(1)测试上限值 2 n − 3 2n - 3 2n−3，在本例中为 17 17 17

#include <iostream>
#include <assert.h>
using namespace std;
class CPrefixSorting {
public:
    CPrefixSorting() {
        m_nCakeCnt = 0;
        m_nMaxSwap = 0;
    }
    ~CPrefixSorting() {
        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* m_CakeArray, int m_nCakeCnt, int* m_SwapArray, int m_nMaxSwap) {
        int t;
        for (int i = 0; i < m_nMaxSwap; ++i) {
            for (int j1 = 0, j2 = m_SwapArray[i]; j1 < j2; ++j1, --j2) {
                t = m_CakeArray[j1];
                m_CakeArray[j1] = m_CakeArray[j2];
                m_CakeArray[j2] = t;
            }
            for (int k = 0; k < m_nCakeCnt; ++k) {
                cout << m_CakeArray[k] << " ";
            }
            cout << endl;
        }
    }
    /*
     * 输出烙饼具体翻转次数
     */
    void Output() {
        for (int i = 0; i < m_nMaxSwap; ++i) {
            cout << m_SwapArray[i] << " ";
        }
        cout << endl << "Search Times: " << m_nSearch << endl;
        cout << "Total Swap times = " << m_nMaxSwap << endl;  

        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 < nCakeCnt; ++i) {
            m_CakeArray[i] = pCakeArray[i];
        }

        //设置最多交换次数信息
        m_nMaxSwap = UpperBound(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 UpperBound(int nCakeCnt) {
        return 2 * nCakeCnt - 3;
    }

    /*
     * 寻找当前翻转的下界
     */
    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++;
        }
        if (pCakeArray[nCakeCnt - 1] != nCakeCnt - 1)
            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) {
            Reverse(0, i);
            m_ReverseCakeArraySwap[step] = i;  //记录交换的烙饼
            Search(step + 1);
            Reverse(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 Reverse(int nBegin, int nEnd) {
        assert(nBegin < nEnd);
        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;
        }
    }

private:
    int* m_CakeArray;  //烙饼信息数组
    int m_nCakeCnt;    //烙饼个数
    int m_nMaxSwap;   //最多交换次数

    int* m_SwapArray;  //交换结果数组

    int* m_ReverseCakeArray;  //当前翻转烙饼信息数组
    int* m_ReverseCakeArraySwap;  //当前翻转烙饼交换结果数组
    int m_nSearch;  //当前搜索次数信息
};

int main() {
    CPrefixSorting test;
    int a[10] = {3, 2, 1, 6, 5, 4, 9, 8, 7, 0};
    test.Run(a, 10);
    test.Output();
    return 0;
}

测试结果：搜索次数 2683 2683 2683

编程之美(三)一摞烙饼的排序

(2)适当降低上限值，设为 18 / 11 ∗ n 18/11 * n 18/11∗n (很早之前的研究值，最新的找不到。。。)

测试结果：搜索次数为 1045 1045 1045

编程之美(三)一摞烙饼的排序

(3)限定上限值，设为 10 10 10

测试结果：搜索次数 1045 1045 1045

编程之美(三)一摞烙饼的排序

编程之美(三)一摞烙饼的排序

1. 最简单的翻转方案

2. 确定搜索方式

3. 深度优先搜索剪枝策略

4. 确定下限值

5. 程序编写

继续阅读

Java 并发 --- Semaphore源码分析

Java 并发 ---中断机制

hiho一下连通性·三强连通分量

Java 并发 --- Exchanger源码分析

hdu 2817 A sequence of numbers （快速幂） A sequence of numbers

springboo2.x权限 demo（shiro,sprng security,oauth2）

亲自动手画红黑树

Java 并发 --- CopyOnWriteArrayList 源码分析

Java 多线程 --- FutureTask 源码分析

【编程之美】高效率的安排见面会

Java 线程池 --- ThreadPoolExecutor源码分析

编程之美(六)饮料供货