<P>不論是哪種全排列生成算法，都遵循著“原排列”→“原中介數(shù)”→“新中介數(shù)”→“新排列”的過程。</P><P>其中中介數(shù)依據(jù)算法的不同會的到遞增進位制數(shù)和遞減進位制數(shù)。</P><P>關(guān)于排列和中介數(shù)的一一對應(yīng)性的證明我們不做討論，這里僅僅給出了排列和中介數(shù)的詳細映射方法。</P>

void next_Permutations_by_increDecimal(int dataArr[],int size){
 int i;
 int *resultArr = new int[size];
 int index = 0;
 map<int,int>::iterator iter;
    //第一步 求出中介數(shù)
 //由大到小，得到并記錄當前排列中，數(shù)字i的右邊比其小的數(shù)的個數(shù)
    map<int,int> agentMap;
 for(i=0; i<size; ++i){
   agentMap.insert(valType(dataArr[i],count(dataArr,i,size,dataArr[i])));
 }
 qsort(dataArr,0,size-1);
    //第二步 得到新的中介數(shù),在舊的中介數(shù)的基礎(chǔ)上，根據(jù)遞增進位制數(shù)法加1
  while (true){
     ++countNum;
     next_inter_num(dataArr,agentMap);
     //第三步 根據(jù)新的中介數(shù)得到新的排列
     index = size -1;
     //清空記錄當前排列的數(shù)組，以存放新產(chǎn)生的排列
     for(i=0; i<size; ++i){
      resultArr[i] = 0;
     }
     while(true){
      iter = agentMap.find(dataArr[index]);
      valType value = *iter;
      resultArr[getNextPosition(resultArr,size,value.second,0)] = dataArr[index];
      --index;
      if(index == 0) break;
     }
     //將最后一個空位置為最小數(shù)
     i = 0;
     while(true){
      if(resultArr[i] != 0){
     ++i;
      }else{
       resultArr[i] = dataArr[index];
       break;
      }
     }
     print(resultArr,size);
     bool flag = true;
     for(i=1; i<size; ++i){
      if(resultArr[i] > resultArr[i-1]){
       flag = false;
       break;
      } 
     }
    if(flag) break;  
 } 
   delete []  resultArr;
}
void next_inter_num(int dataArr[],map<int,int>& agentMap){
 map<int,int>::iterator iter;
  //temp當前位需要增加得值，tmpResult為temp與當前位的值之和，start為末位開始的進制
    int start = 2,temp=1,tmpResult;
    int index = 1; //數(shù)組中的第一個數(shù)位最小數(shù)
 while(true){
   iter = agentMap.find(dataArr[index]);
   valType value = *iter;
   tmpResult = value.second + temp;
   if(tmpResult < start){
    //已經(jīng)不產(chǎn)生進位
      agentMap.erase(dataArr[index]);
   agentMap.insert(valType(dataArr[index],tmpResult));
   break;
   }else{ 
   agentMap.erase(dataArr[index]);
   agentMap.insert(valType(dataArr[index],tmpResult % start));
   temp = tmpResult / start;
    ++start;
   }
   ++index;
 }
}

void next_Permutations_by_DecreDecimal(int dataArr[],int size){
 //創(chuàng)建一個結(jié)果數(shù)組，用來記錄下一個排列
 int *resultArr = new int[size];
 int i;
    //第一步 求出中介數(shù)
    map<int,int> agentMap;
 for(i=0; i<size; ++i){
    int nums = count(dataArr,i,size,dataArr[i]);
    agentMap.insert(valType(dataArr[i],nums));
 }
 //第二步 求新的中介數(shù) 此處最低位進制最高，故不會頻繁產(chǎn)生進位，性能應(yīng)該優(yōu)于遞增進位
 //最低位進制為9，向前依次遞減
 int start = size,temp = 1;
 int tmpResult;
 int index = size-1;//中介數(shù)末位數(shù)位數(shù)字序列中最大的數(shù)右邊比其小的數(shù)
 map<int,int>::iterator iter;
 qsort(dataArr,0,size-1);
 while (true){
   ++countNum; //全局變量 記錄排列個數(shù)
         next_inter_num(dataArr,agentMap,size);
   index = size -1;
  //第三步 根據(jù)產(chǎn)生的中介數(shù)得到新的排列
  for(i=0; i<size; ++i){
   resultArr[i] = 0;
  }
    while(true){
   iter = agentMap.find(dataArr[index]);
   valType value = *iter;
   //找到下一個填充空位
   resultArr[getNextPosition(resultArr,size,value.second,0)] = dataArr[index];
   --index;
   if(index == 0) break;
    }
    i = 0;
    while(true){
     if(resultArr[i] != 0){
      ++i;
     }else{
      resultArr[i] = dataArr[index];
      break;
     }
    }
    print(resultArr,size);
    bool flag = true;
    for(i=1; i<size; ++i){
     if(resultArr[i] > resultArr[i-1]){
      flag = false;
      break;
     } 
    }
    if(flag) break;
 }
   delete [] resultArr;
}
void next_inter_num(int dataArr[],map<int,int> &agentMap,int size){
 int start = size,temp = 1;
 int tmpResult;
 int index = size-1;//中介數(shù)末位數(shù)位數(shù)字序列中最大的數(shù)右邊比其小的數(shù)
 map<int,int>::iterator iter;
    while(true){
   iter = agentMap.find(dataArr[index]);
   valType value = *iter;
   tmpResult = value.second + temp;
   if(tmpResult < start){
   //沒有產(chǎn)生進位，直接改寫末位值
      agentMap.erase(dataArr[index]);
   agentMap.insert(valType(dataArr[index],tmpResult));
   break;
   }else{ 
   //產(chǎn)生進位
   agentMap.erase(dataArr[index]);
   agentMap.insert(valType(dataArr[index],tmpResult % start));
   tmpResult = tmpResult / start;
   --start;
   } 
   --index;
 }
}