三种全排序算法详解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了三种全排序算法详解,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5306字,纯文字阅读大概需要8分钟。
内容图文
1、全排列的非去重递归算法
算法思路:全排列可以看做固定前i位,对第i+1位之后的再进行全排列,比如固定第一位,后面跟着n-1位的全排列。那么解决n-1位元素的全排列就能解决n位元素的全排列了,这样的设计很容易就能用递归实现。
附代码段:
void permutation1(char* str,int sbegin,int send) //全排列的非去重递归算法 { if( sbegin == send) //当 sbegin = send时输出 { for(int i = 0;i <= send; i++) //输出一个排列 cout << str[i]; cout << endl; } else { for(int i = sbegin; i <= send; i++) //循环实现交换和sbegin + 1之后的全排列 { swap(str[i],str[sbegin]); //把第i个和第sbegin进行交换 permutation1(str,sbegin + 1,send); swap(str[i],str[sbegin]); //交换回来 } } }
2、全排列的去重递归算法
当第i位与i+n位交换时,i到i+n位中不能有与i+n位相同的字符
比如说23560678,当第三位5与第六位6交换时,中间不能有6,这里有6所以不进行交换
附代码段:
bool comparesub(char* str,int sbegin,int send) //比较函数,[sbegin,send)中是否有与send的值相等得数 { for(int i = sbegin; i < send; i++) if(str[i] == str[send]) return false; return true; } void permutation2(char* str,int sbegin,int send) //全排列的去重递归算法 { if(sbegin == send) //当 sbegin = send时输出 { for(int i = 0; i <= send; i++) //输出一个排列 cout << str[i]; cout << endl; } else { for(int i = sbegin; i <= send; i++) { if(comparesub(str,sbegin,i)) //如果sbeing到i没有重复数字 { swap(str[i],str[sbegin]); //把第i个和第sbegin进行交换 permutation2(str,sbegin + 1,send); swap(str[i],str[sbegin]); //交换回来 } } } }
3、全排列的去重非递归算法
算法思路:先排序得到递增序列,从字符串尾部向前找第一双相邻的递增字符,称前一个数为替换字符,替换字符的下标称为替换点,再从该字符后面找到一个比替换字符大的最小的字符(因为有递增关系,所以这个数必然存在的),然后再将替换点后的字符串逆置。循环到最大排序后,逆置并结束算法
例:字符串2568710 先排序得到0125678找到一双相邻递增字符,78,再在7后面的字符里找到符合算法的字符8,替换得到字符串0125687,再将7后面的字符串逆置,得到0125687
附代码段:
void Reverse(char* a,char* b) //逆置函数 { while(a < b) { char tmp = *a; *a = *b; *b = tmp; a++; b--; } } bool next_permutation3(char* str) //找到一个满足算法的序列 { int i; int slen = strlen(str); //str长度 for(i = slen - 1; i >= 1; i--) //循环找出一双相邻递增字符 { if(str[i - 1] < str[i]) break; } if(!i) //如果i=0,证明没有一双相邻递增字符,那么也就说明整个字符串是最大排列 { return false; //结束算法 } else { char tmp = str[i - 1]; //替换字符 int pos = i; //比替换字符大的最小的字符位置 for(int j = i; j < slen; j++) { if(str[j] > tmp && str[j] <= str[pos]) //从替换字符后面找到一个比替换字符大的最小的字符 pos = j; } str[i - 1] = str[pos]; str[pos] = tmp; //字符替换 char *p = str + i; char *q = str + (slen - 1); Reverse(p,q); //将替换点后的字符串逆置 return true; //下一个 } } int qsortcmp(const void * pa,const void * pb) //比较函数 { return *(char*)pa - *(char*)pb; //先强制类型转化,再取值 } void permutation3(char* str) //全排列的去重非递归算法 { qsort(str,strlen(str),sizeof(char),qsortcmp); //快速排序 do { for(int i = 0; i < strlen(str); i++) //输出一个排列 cout << str[i]; cout << endl; }while(next_permutation3(str)); }
4、源代码
#include <iostream> #include <cstring> #include <cstdlib> using namespace std; /* 算法思路:全排列可以看做固定前i位,对第i+1位之后的再进行全排列,比如固定第一位,后面跟着n-1位的全排列。那么解决n-1位元素的全排列就能解决n位元素的全排列了,这样的设计很容易就能用递归实现。 */ void permutation1(char* str,int sbegin,int send) //全排列的非去重递归算法 { if( sbegin == send) //当 sbegin = send时输出 { for(int i = 0;i <= send; i++) //输出一个排列 cout << str[i]; cout << endl; } else { for(int i = sbegin; i <= send; i++) //循环实现交换和sbegin + 1之后的全排列 { swap(str[i],str[sbegin]); //把第i个和第sbegin进行交换 permutation1(str,sbegin + 1,send); swap(str[i],str[sbegin]); //交换回来 } } } /* 序列有时候可能有重复的字符,当需要输出去重全排列时,就可以采取以下方法 当第i位与i+n位交换时,i到i+n位中不能有与i+n位相同的字符 比如说23560678,当第三位5与第六位6交换时,中间不能有6,这里有6所以不进行交换 */ bool comparesub(char* str,int sbegin,int send) //比较函数,[sbegin,send)中是否有与send的值相等得数 { for(int i = sbegin; i < send; i++) if(str[i] == str[send]) return false; return true; } void permutation2(char* str,int sbegin,int send) //全排列的去重递归算法 { if(sbegin == send) //当 sbegin = send时输出 { for(int i = 0; i <= send; i++) //输出一个排列 cout << str[i]; cout << endl; } else { for(int i = sbegin; i <= send; i++) { if(comparesub(str,sbegin,i)) //如果sbeing到i没有重复数字 { swap(str[i],str[sbegin]); //把第i个和第sbegin进行交换 permutation2(str,sbegin + 1,send); swap(str[i],str[sbegin]); //交换回来 } } } } /* 算法思路:先排序得到递增序列,从字符串尾部向前找第一双相邻的递增字符,称前一个数为替换字符,替换字符的下标称为替换点,再从该字符后面找到一个比替换字符大的最小的字符(因为有递增关系,所以这个数必然存在的),然后再将替换点后的字符串逆置。循环到最大排序后,逆置并结束算法 例:字符串2568710 先排序得到0125678找到一双相邻递增字符,78,再在7后面的字符里找到符合算法的字符8,替换得到字符串0125687,再将7后面的字符串逆置,得到0125687 */ void Reverse(char* a,char* b) //逆置函数 { while(a < b) { char tmp = *a; *a = *b; *b = tmp; a++; b--; } } bool next_permutation3(char* str) //找到一个满足算法的序列 { int i; int slen = strlen(str); //str长度 for(i = slen - 1; i >= 1; i--) //循环找出一双相邻递增字符 { if(str[i - 1] < str[i]) break; } if(!i) //如果i=0,证明没有一双相邻递增字符,那么也就说明整个字符串是最大排列 { return false; //结束算法 } else { char tmp = str[i - 1]; //替换字符 int pos = i; //比替换字符大的最小的字符位置 for(int j = i; j < slen; j++) { if(str[j] > tmp && str[j] <= str[pos]) //从替换字符后面找到一个比替换字符大的最小的字符 pos = j; } str[i - 1] = str[pos]; str[pos] = tmp; //字符替换 char *p = str + i; char *q = str + (slen - 1); Reverse(p,q); //将替换点后的字符串逆置 return true; //下一个 } } int qsortcmp(const void * pa,const void * pb) //比较函数 { return *(char*)pa - *(char*)pb; //先强制类型转化,再取值 } void permutation3(char* str) //全排列的去重非递归算法 { qsort(str,strlen(str),sizeof(char),qsortcmp); //快速排序 do { for(int i = 0; i < strlen(str); i++) //输出一个排列 cout << str[i]; cout << endl; }while(next_permutation3(str)); } int main() { char str[] = "1223"; //测试数据 // permutation1(str,0,strlen(str) - 1); // permutation2(str,0,strlen(str) - 1); permutation3(str); return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/q547550831/article/details/47359119
内容总结
以上是互联网集市为您收集整理的三种全排序算法详解全部内容,希望文章能够帮你解决三种全排序算法详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。