使用C++实现全排列算法的方法详解
<P>不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。</P><P>其中中介数依据算法的不同会的到递增进位制数和递减进位制数。</P><P>关于排列和中介数的一一对应性的证明我们不做讨论,这里仅仅给出了排列和中介数的详细映射方法。</P>
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字,如
接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作一个有序的数字集合。如果规定递增进位制和递减进位制数的
例如序号100的递增进位制数就是4020,即4*4!+ 0*3!+ 2*2!+ 0*1!=100。将一个序号转换成其递增进位制数首先需要找到一个比序号小的最大阶乘数(即1、2、6、24、120、720……),
递减进位制数(
例如序号
关于递增进位制和递减进位制需要注意的重点:一是其加减法的进位需要小心;二是序号和数字的转换。除了
从现在开始我们将详细介绍六种排列生成算法。具体的理论介绍将被忽略,下文所注重的就是如何将排列映射为中介数以及如何将中介数还原为排列。
我全部以求
还原方法:我们设新中介数的位置号从左向右依次是
映射方法:
voidnext_Permutations_by_increDecimal(intdataArr[],intsize){
inti;
int*resultArr=newint[size];
intindex=0;
map<int,int>::iteratoriter;
//第一步求出中介数
//由大到小,得到并记录当前排列中,数字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]);
valTypevalue=*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);
boolflag=true;
for(i=1;i<size;++i){
if(resultArr[i]>resultArr[i-1]){
flag=false;
break;
}
}
if(flag)break;
}
delete[] resultArr;
}
voidnext_inter_num(intdataArr[],map<int,int>&agentMap){
map<int,int>::iteratoriter;
//temp当前位需要增加得值,tmpResult为temp与当前位的值之和,start为末位开始的进制
intstart=2,temp=1,tmpResult;
intindex=1;//数组中的第一个数位最小数
while(true){
iter=agentMap.find(dataArr[index]);
valTypevalue=*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;
}
}
映射方法:递减进位制的映射方法刚好和递增进位制相反,即按照从
还原方法:递减进位制中介数的还原方法也刚好和递增进位制中介数相反。递增进位制还原方法是按照从中介数最高位(左侧)到最低位(右侧)的顺序来填数。而递减仅位置还原方法则从中介数的最低位向最高位进行依次计数填空。例如对于新中介数
C++实现代码:
voidnext_Permutations_by_DecreDecimal(intdataArr[],intsize){
//创建一个结果数组,用来记录下一个排列
int*resultArr=newint[size];
inti;
//第一步求出中介数
map<int,int>agentMap;
for(i=0;i<size;++i){
intnums=count(dataArr,i,size,dataArr[i]);
agentMap.insert(valType(dataArr[i],nums));
}
//第二步求新的中介数此处最低位进制最高,故不会频繁产生进位,性能应该优于递增进位
//最低位进制为9,向前依次递减
intstart=size,temp=1;
inttmpResult;
intindex=size-1;//中介数末位数位数字序列中最大的数右边比其小的数
map<int,int>::iteratoriter;
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]);
valTypevalue=*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);
boolflag=true;
for(i=1;i<size;++i){
if(resultArr[i]>resultArr[i-1]){
flag=false;
break;
}
}
if(flag)break;
}
delete[]resultArr;
}
voidnext_inter_num(intdataArr[],map<int,int>&agentMap,intsize){
intstart=size,temp=1;
inttmpResult;
intindex=size-1;//中介数末位数位数字序列中最大的数右边比其小的数
map<int,int>::iteratoriter;
while(true){
iter=agentMap.find(dataArr[index]);
valTypevalue=*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;
}
}
还原方法:还原方法为映射方法的逆过程。你可以先写出辅助数字
C++实现:
voidnext_Permutations_by_DicOrder(intdataArr[],intsize){
intkey=0;
intindex,temp,end,left,right;
inti;
boolflag;
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;
}
}
}
回溯法:
voidnext_Permutations_by_backtrack(intdataArr[],intsize){
//创建结果数组
int*resultArr=newint[size+1];
backTrack(1,size+1,resultArr,dataArr);
delete[]resultArr;
}
//剪枝函数
boolplace(intk,intresultArr[])
{
for(intj=1;j<k;j++){
if(resultArr[j]==resultArr[k]){
returnfalse;
}
}
returntrue;
}
voidbackTrack(intt,intsize,intresultArr[],intdataArr[])
{
if(t>size-1){
++countNum;
for(inti=1;i<size;i++){
cout<<resultArr[i]<< "";
}
cout<<endl;
}else{
for(inti=1;i<size;i++){
resultArr[t]=dataArr[i-1];
if(place(t,resultArr)){
backTrack(t+1,size,resultArr,dataArr);
}
}
}
}
相关文章
- EasyC++85,私有继承(三)
- 初识 CGO - 利用 CGO 使用 C++ STL
- C++反射 - 反射信息的自动生成
- 现代c++中实现精确延时方法总结
- C++动态库和静态库_动态库和静态库调用方法
- c++的链表-C++链表
- c++的链表-链表入门(C++)
- C/C++ Qt 选择夹TabWidget组件应用
- c++字符串
- 【转】c++中的new/delete详解编程语言
- C++ string支持迭代器方法详解
- C++ 之父 Stroustrup 推出“ C++ 核心准则”
- 解决C++中重定义的方法总结
- 深入分析C++中执行多个exe文件方法的批处理代码介绍
- 用C++实现,将一句话里的单词进行倒置的方法详解
- C++算法之海量数据处理方法的总结分析
- C++实现基数排序的方法详解
- android杂记:C++文件的添加log方法分享
- c++中的4种类型转化方式详细解析
- 安卓应用开发通过java调用c++jni的图文使用方法
- c++连接mysql数据库的两种方法(ADO连接和mysqlapi连接)
- C++实现修改函数代码HOOK的封装方法
- C++实现读取特定路径下文件夹及文件名的方法
- 让Sqlite脱离VC++Runtime独立运行的方法
- VC++实现程序开机启动运行的方法
- C++实现闹钟程序的方法
- C++堆排序算法的实现方法
- VC++中内存对齐实例教程
- C++循环链表之约瑟夫环的实现方法
- C++指向函数的指针用法详解