使用C++实现全排列算法的方法详解

代码如下:

<P>不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。</P><P>其中中介数依据算法的不同会的到递增进位制数和递减进位制数。</P><P>关于排列和中介数的一一对应性的证明我们不做讨论,这里仅仅给出了排列和中介数的详细映射方法。</P>

· 递增进位制和递减进位制数 
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字,如2进制,10进制等。m位n进制数可以表示的数字是m*n个。而m位递增或递减进位制数则可以表示数字m!个。例如递增进位制数4121,它的进制从右向左依次是2、3、4、5。即其最高位(就是数字4那位)最大值可能是4;第三高位最大可能是3;第二高位最大可能是2;最末位最大可能是1。如果将4121加上1的话,会使最末位得到0,同时进位;第二位的2与进位相加,也会得到0,同时进位;第三位的1与进位相加得到2,不再进位。最终得到结果是4200。递减进位制的道理是一样的,只不过进制从右向左依次是9、8、7、6……,正好与递增进位制相反。很明显,递减进位制的一个最大的好处就是加法不易进位,因为它在进行加法最频繁的末几位里(最右边)进制比较大。

接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作一个有序的数字集合。如果规定递增进位制和递减进位制数的0的序号是十进制0,递增进位制数的987654321和递减进位制数的123456789对应十进制序号362880(即9!),则可以整理一套对应法则。其中,递增进位制数(a1 a2 a3 a4 a5 a6 a7 a8 a9)为:

a1*9! + a2*8! + ….+ a8*2! + a9*1! = 序号

例如序号100的递增进位制数就是4020,即4*4!+ 0*3!+ 2*2!+ 0*1!=100。将一个序号转换成其递增进位制数首先需要找到一个比序号小的最大阶乘数(即1、2、6、24、120、720……),对其进行整数除得到递增进位制的第一位;将除法的余数反复应用这个方法(当然,之后选择的余数是小一级的阶乘数),直到余数为0。

递减进位制数(a1 a2 a3 a4 a5 a6 a7 a8 a9)为:

(((((((((a1 * 1 + a2) * 2 + a3) * 3 + …… + a7) * 8 + a8) * 9 + a9= 序号

例如序号100的递减进位制数就是131(a7 a8 a9, 即从后对齐),即 (1*8 + 3)*9 + 1 = 100。将一个序号转换成其递减进位制数,需要对序号用9取余数,就可以得到递减进位制的最末位(这点和递增进位制先算出最高位相反)。用余下的数的整数除结果重复此过程(当然,依次对8、7、6……取余),直到余数为0。

关于递增进位制和递减进位制需要注意的重点:一是其加减法的进位需要小心;二是序号和数字的转换。除了100之外,常见的转换有:999的递增数是121211,递减数是1670;99的递增数是4011,递减数是130。大家可以以此为参考测试自己是否真正理解了计算的方法。下文将省略递增进位制或递减进位制的详细计算过程。

从现在开始我们将详细介绍六种排列生成算法。具体的理论介绍将被忽略,下文所注重的就是如何将排列映射为中介数以及如何将中介数还原为排列。

我全部以求839647521的下100个排列为例。

· 递增进位排列生成算法
映射方法:将原排列按照从9到2的顺序,依次查看其右侧比其小的数字的个数。这个个数就是中介数的一位。例如对于原排列839647521。9的右侧比9小的数字有6个,8的右侧比8小的数字有7个,7的右侧比7小的数字有3个,……2的右侧比2小的数字有1个。最后得到递增进制中介数67342221。(此中介数加上100的递增进制数4020得到新的中介数67351311)

还原方法:我们设新中介数的位置号从左向右依次是9、8、7、6、5、4、3、2。在还原前,画9个空格。对于每一个在位置x的中介数y,从空格的右侧向左数y个未被占用的空格。在第y+1个未占用的空格中填上数字x。重复这个过程直到中介数中所有的位都被数完。最后在余下的最后一个空格里填上1,完成新排列的生成。以新中介数67351311为例,我给出了详细的恢复步骤。其中红色数字代表新填上的数字。最后得到新排列869427351。

代码如下:

void next_Permutations_by_increDecimal(int dataArr[],int size){
 int i;
 int *resultArr = new int[size];
 int index = 0;
 map<int,int>::iterator iter;
    //第一步 求出中介数
 //由大到小,得到并记录当前排列中,数字i的右边比其小的数的个数
    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);
    //第二步 得到新的中介数,在旧的中介数的基础上,根据递增进位制数法加1
  while (true){
     ++countNum;
     next_inter_num(dataArr,agentMap);
     //第三步 根据新的中介数得到新的排列
     index = size -1;
     //清空记录当前排列的数组,以存放新产生的排列
     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){
 map<int,int>::iterator iter;
  //temp当前位需要增加得值,tmpResult为temp与当前位的值之和,start为末位开始的进制
    int start = 2,temp=1,tmpResult;
    int index = 1; //数组中的第一个数位最小数
 while(true){
   iter = agentMap.find(dataArr[index]);
   valType value = *iter;
   tmpResult = value.second + temp;
   if(tmpResult < start){
    //已经不产生进位
      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;
 }
}

· 递减进位排列生成算法
映射方法:递减进位制的映射方法刚好和递增进位制相反,即按照从9到2的顺序,依次查看其右侧比其小数字的个数。但是,生成中介数的顺序不再是从左向右,而是从右向左。生成的递减进制中介数刚好是递增进位排列生成算法得到中介数的镜像。例如839647521的递减进制中介数就是12224376。(此中介数加上100的递减进制数131后得到新中介数12224527) 

还原方法:递减进位制中介数的还原方法也刚好和递增进位制中介数相反。递增进位制还原方法是按照从中介数最高位(左侧)到最低位(右侧)的顺序来填数。而递减仅位置还原方法则从中介数的最低位向最高位进行依次计数填空。例如对于新中介数12224527,我给出了详细的还原步骤。红色代表当前正在填充的空格。最终得到新排列397645821。

C++实现代码:


代码如下:

void next_Permutations_by_DecreDecimal(int dataArr[],int size){
 //创建一个结果数组,用来记录下一个排列
 int *resultArr = new int[size];
 int i;
    //第一步 求出中介数
    map<int,int> agentMap;
 for(i=0; i<size; ++i){
    int nums = count(dataArr,i,size,dataArr[i]);
    agentMap.insert(valType(dataArr[i],nums));
 }
 //第二步 求新的中介数 此处最低位进制最高,故不会频繁产生进位,性能应该优于递增进位
 //最低位进制为9,向前依次递减
 int start = size,temp = 1;
 int tmpResult;
 int index = size-1;//中介数末位数位数字序列中最大的数右边比其小的数
 map<int,int>::iterator iter;
 qsort(dataArr,0,size-1);
 while (true){
   ++countNum; //全局变量 记录排列个数
         next_inter_num(dataArr,agentMap,size);
   index = size -1;
  //第三步 根据产生的中介数得到新的排列
  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;//中介数末位数位数字序列中最大的数右边比其小的数
 map<int,int>::iterator iter;
    while(true){
   iter = agentMap.find(dataArr[index]);
   valType value = *iter;
   tmpResult = value.second + temp;
   if(tmpResult < start){
   //没有产生进位,直接改写末位值
      agentMap.erase(dataArr[index]);
   agentMap.insert(valType(dataArr[index],tmpResult));
   break;
   }else{ 
   //产生进位
   agentMap.erase(dataArr[index]);
   agentMap.insert(valType(dataArr[index],tmpResult % start));
   tmpResult = tmpResult / start;
   --start;
   } 
   --index;
 }
}

· 字典全排列生成法
映射方法:将原排列数字从左到右(最末尾不用理会),依次查看数字右侧比其小的数字有几个,个数就是中介数的一位。例如,对于排列839647521。最高位8右侧比8小的有7个数字,次高位3右侧比3小的数字有2个,再次位的9的右侧比9小的有6个数字,……,2的右侧比2小的数有1个。得到递增进制中介数72642321。(此中介数加上100的递增进进制数4020后得到新中介数72652011)

还原方法:还原方法为映射方法的逆过程。你可以先写出辅助数字1 2 3 4 5 6 7 8 9,以及9个空位用于填充新排列。然后从新中介数的最高位数起。例如新中介数最高位是x,你就可以从辅助数字的第一个没有被使用的数字开始数起,数到x。第x+1个数字就应当是空位的第一个数字。我们将此数字标为“已用”,然后用其填充左起第一个空位。然后,再看新中介数的次高位y,从辅助数字的第一个未用数字数起,数到一。第y+1个数字就是下一个空位的数字。我们将此数字标为“已用”,然后用其填充左起第二个空位。依此类推,直到最后一个中介数中的数字被数完为止。例如对于新中介数72652011,我们给出其辅助数字和空位的每一步的情况。其中红色的数字代表“正在标记为已用”,“已用”的数字不会再被算在之后的计数当中。当新中介数中所有的数字都被数完了,辅助数字中剩下的唯一数字将被填入最后的空位中。最终得到新排列839741562。

C++实现:


代码如下:

void next_Permutations_by_DicOrder(int dataArr[],int size){
 int key = 0;
 int index,temp,end,left,right;
 int i;
 bool flag ;
 while(true){  
  ++countNum;
     print(dataArr,size);
  flag = true;
  index = 0,temp = 0,end=8,left = right = 0;
  //从当前排列末尾向前找到第一次出现下降的点
  for(i = size-1; i > 0; i--){
   if(dataArr[i] > dataArr[i-1]){
    key = i-1; //K记录下降的点
    flag = false;
    break;
   }   
  }
  //如果已经是由高到低有序,则操作完成
  if(flag)
   break;
  index = key + 1;
        //找到后缀中比第一次下降点的数大的数中最小的数
  while(dataArr[key] < dataArr[index] && index < size){
      ++index;
  }
        index --;
  //将找到的数和第一次出现下降的点交换
  temp = dataArr[key];
  dataArr[key] = dataArr[index];
  dataArr[index] = temp;
  left = key+1;
  right = size - 1;
  //将下降点后面的数逆转
  while(left < right){
   temp = dataArr[left];
   dataArr[left] = dataArr[right];
   dataArr[right] = temp;
   ++left;
   --right;
  }
 }
}

回溯法:


代码如下:

void next_Permutations_by_backtrack(int dataArr[],int size){
 //创建结果数组
    int *resultArr = new int[size+1];
 backTrack(1,size+1,resultArr,dataArr);
 delete [] resultArr;
}
//剪枝函数
bool place(int k,int resultArr[])
{
 for (int j = 1; j < k; j++) {
  if (resultArr[j] == resultArr[k]) {
   return false;
  }
 }
 return true;
}
void backTrack(int t,int size,int resultArr[],int dataArr[])
{
 if (t > size-1) {
  ++ countNum;
  for(int i = 1; i < size; i++) {
   cout << resultArr[i] <<  " ";
  }
  cout << endl;
 } else {
  for(int i = 1; i < size; i++) {
   resultArr[t] = dataArr[i-1];
   if (place(t,resultArr)) {
    backTrack(t+1,size,resultArr,dataArr);
   }
  }
 }
}

(0)

相关推荐

  • 基于C++实现的各种内部排序算法汇总

    提起排序算法相信大家都不陌生,或许很多人已经把它们记得滚瓜烂熟,甚至随时可以写出来.是的,这些都是最基本的算法.这里就把各种内部排序算法总结归纳了一下,包括插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序.(另:至于堆排序算法,前面已经有一篇文章针对堆排序的算法实现做了详细的描述) C++实现代码如下: /*******************************************************

  • 利用C++的基本算法实现十个数排序

    冒泡排序法原理:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 冒泡排序算法的运作如下:1.比较相邻的元素.如果第一个比第二个大,就交换他们两个. 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 3.针对所有的元素重复以上的步骤,除了最后一个. 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 示例代码:

  • C++线性时间的排序算法分析

    前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序(可以参考前一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较. 本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序.它们将突破比较排序的Ω(nlgn)下界,以线性时间运行. 一.比较排序算法的时间下界 所谓的比较排序是指通过比较来决定元素间的相对次序. "定理:对于含n个元素的一个输入序列,

  • C++插入排序算法实例

    插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

  • C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • C++实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • 全排列算法的非递归实现与递归实现的方法(C++)

    (一)非递归全排列算法基本思想是:    1.找到所有排列中最小的一个排列P.    2.找到刚刚好比P大比其它都小的排列Q,    3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P =  A1A2A3An ( Ai!=Aj , (1<=i<=n  , 1<=j<=n, i != j  ) )找到P的一个最小排列Pmin = P1P2P3Pn  有  Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目

  • C++冒泡排序算法实例

    冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

  • C++简单实现的全排列算法示例

    本文实例讲述了C++简单实现的全排列算法.分享给大家供大家参考,具体如下: #include "stdafx.h" #include <string> #include <algorithm> #include <iostream> void func(const char *str_in) { std::string str(str_in); std::sort(str.begin(),str.end()); do { std::cout<&

  • C++实现各种排序算法类汇总

    C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

  • C++选择排序算法实例

    选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

随机推荐