/****************************************************************/
//
// 烙饼排序实现
//
/****************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <assert.h>
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;
}
if(m_nCost!=NULL) delete m_nCost;
if(m_flags!=NULL) delete m_flags;
}
//
// 计算烙饼翻转信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Run(int* pCakeArray, int nCakeCnt)
{
Init(pCakeArray, nCakeCnt);
m_nSearch = 0;
Search(0);
}
//
// 输出烙饼具体翻转的次数
//
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);
}
private:
//
// 初始化数组信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Init(int* pCakeArray, int nCakeCnt)
{
int i;
assert(pCakeArray != NULL);
assert(nCakeCnt > 0);
m_nCakeCnt = nCakeCnt;
// 初始化烙饼数组
m_CakeArray = new int[m_nCakeCnt];
assert(m_CakeArray != NULL);
for(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);
//init cost info
m_nCost = new int[nCakeCnt];
assert(m_nCost != NULL);
m_flags = new int[nCakeCnt];
// 初始化中间交换结果信息
m_ReverseCakeArray = new int[m_nCakeCnt];
for(i = 0; i < m_nCakeCnt; i++)
{
m_ReverseCakeArray[i] = m_CakeArray[i];
}
m_ReverseCakeArraySwap = new int[m_nMaxSwap];
}
//
// 寻找当前翻转的上界
//
//
int UpBound(int nCakeCnt)
{
return 2*(nCakeCnt-1);
}
//
// 寻找当前翻转的下界
//
//
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;
int j;
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;
}
// 递归进行翻转
//
setFlags();
for(i = 1; i < m_nCakeCnt; i++)
{
if(m_flags[i]==1){
Revert(0, i);//we must revert from the first cake.
m_ReverseCakeArraySwap[step] = i;
Search(step + 1);
Revert(0, i);
}
}
clearFlags();
}
void clearFlags(){
int i;
for(i = 1; i < m_nCakeCnt; i++)
m_flags[i]=1;
}
void setFlags()
{
int i;
int min;
for(i = 1; i < m_nCakeCnt; i++)
{
Revert(0, i);
m_nCost[i] = calcCost(m_ReverseCakeArray,m_nCakeCnt);
Revert(0, i);
}
min = m_nCost[1];
for (i=1;i<m_nCakeCnt;i++){
if(m_nCost[i]<min) min=m_nCost[i];
}
for(i=1;i<m_nCakeCnt;i++){
if(m_nCost[i]==min)
m_flags[i]=1;
else
m_flags[i]=0;
}
}
//
// 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;
}
}
//caculate cost of the node;
int calcCost(int *arr, int count){
int i;
int t;
int ret = 0;
int flag = 0;
i = count;
for(;i>1;i--){
if(!flag && arr[i-1] == i){
continue;
}
t = arr[i-1]-arr[i-2];
if( t==1 || t==-1 ){
continue;
}
ret++;
flag=1;
}
return ret;
}
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; // 当前搜索次数信息
int *m_nCost;
int *m_flags;
};
int main(){
CPrefixSorting cps2;
int cakeArray2[10]={3,2,1,6,5,4,9,8,7,0};
cps2.Run(cakeArray2,10);
cps2.Output();
return 0;
}
|
