常州营销型网站建设,上海搬家公司报价,佛山市创意动力信息科技有限公司,做网站前端全排列在笔试面试中很热门#xff0c;因为它难度适中#xff0c;既可以考察递归实现#xff0c;又能进一步考察非递归的实现#xff0c;便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了#xff0c;因此本文对全排列作下总结帮助…全排列在笔试面试中很热门因为它难度适中既可以考察递归实现又能进一步考察非递归的实现便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处欢迎大家指出。
首先来看看题目是如何要求的百度迅雷校招笔试题。
转载http://blog.csdn.net/hackbuteer1/article/details/7462447
一、字符串的排列 用C写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba 一、全排列的递归实现 为方便起见用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后递归的代码就很容易写出来了 #includeiostream
using namespace std;
#includeassert.hvoid Permutation(char* pStr, char* pBegin)
{assert(pStr pBegin);if(*pBegin \0)printf(%s\n,pStr);else{for(char* pCh pBegin; *pCh ! \0; pCh){swap(*pBegin,*pCh);Permutation(pStr, pBegin1);swap(*pBegin,*pCh);}}
}int main(void)
{char str[] abc;Permutation(str,str);return 0;
}
另外一种写法/prepre namecode classcpppre namecode classcpp//k表示当前选取到第几个数m表示共有多少个数
#include iostream
#include cstring
#include cassert
using namespace std;
void Permutation(char* pStr,int k,int m)
{assert(pStr);if(k m){static int num 1; //局部静态变量用来统计全排列的个数printf(第%d个排列\t%s\n,num,pStr);}else{for(int i k; i m; i){swap(*(pStrk),*(pStri));Permutation(pStr, k 1 , m);swap(*(pStrk),*(pStri));}}
}int main(void)
{char str[] abc;Permutation(str , 0 , strlen(str));return 0;
}如果字符串中有重复字符的话上面的那个方法肯定不会符合要求的因此现在要想办法来去掉重复的数列。二、去掉重复的全排列的递归实现由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了但对212它第二个数与第三个数是不相同的交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。换种思维对122第一个数1与第二个数2交换得到212然后考虑第一个数1与第三个数2交换此时由于第三个数等于第二个数所以第一个数不再与第三个数交换。再考虑212它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。下面给出完整代码 #includeiostreamusing namespace std;#includeassert.h//在[nBegin,nEnd)区间中是否有字符与下标为pEnd的字符相等,也就是在pEnd之前是否有与之相等的数bool IsSwap(char* pBegin , char* pEnd){char *p;for(p pBegin ; p pEnd ; p){if(*p *pEnd)return false;}return true;}void Permutation(char* pStr , char *pBegin){assert(pStr);if(*pBegin \0){static int num 1; //局部静态变量用来统计全排列的个数printf(第%d个排列\t%s\n,num,pStr);}else{for(char *pCh pBegin; *pCh ! \0; pCh) //第pBegin个数分别与它后面的数字交换就能得到新的排列 {if(IsSwap(pBegin , pCh)){swap(*pBegin , *pCh);Permutation(pStr , pBegin 1);swap(*pBegin , *pCh);}}}}int main(void){char str[] baa;Permutation(str , str);return 0;}OK到现在我们已经能熟练写出递归的方法了并且考虑了字符串中的重复数据可能引发的重复数列问题。那么如何使用非递归的方法来得到全排列了三、全排列的非递归实现要考虑全排列的非递归实现先来考虑如何计算字符串的下一个排列。如1234的下一个排列就是1243。只要对字符串反复求出下一个排列全排列的也就迎刃而解了。如何计算字符串的下一个排列了来考虑926520这个字符串我们从后向前找第一双相邻的递增数字20、52都是非递增的26 即满足要求称前一个数字2为替换数替换数的下标称为替换点再从后面找一个比替换数大的最小数这个数必然存在0、2都不行5可以将5和2交换得到956220然后再将替换点后的字符串6220颠倒即得到950226。对于像“4321”这种已经是最“大”的排列采用STL中的处理方法将字符串整个颠倒得到最“小”的排列1234并返回false。 这样只要一个循环再加上计算字符串下一个排列的函数就可以轻松的实现非递归的全排列算法。按上面思路并参考STL中的实现源码不难写成一份质量较高的代码。值得注意的是在循环前要对字符串排序下可以自己写快速排序的代码请参阅《白话经典算法之六 快速排序 快速搞定》也可以直接使用VC库中的快速排序函数请参阅《使用VC库函数中的快速排序函数》。下面列出完整代码
#includeiostream
#includealgorithm
#includecstring
using namespace std;
#includeassert.h//反转区间
void Reverse(char* pBegin , char* pEnd)
{while(pBegin pEnd)swap(*pBegin , *pEnd--);
}
//下一个排列
bool Next_permutation(char a[])
{assert(a);char *p , *q , *pFind;char *pEnd a strlen(a) - 1;if(a pEnd)return false;p pEnd;while(p ! a){q p;p--;if(*p *q) //找降序的相邻2数,前一个数即替换数 {//从后向前找比替换点大的第一个数pFind pEnd;while(*pFind *p)--pFind;swap(*p , *pFind);//替换点后的数全部反转Reverse(q , pEnd);return true;}}Reverse(a , pEnd); //如果没有下一个排列,全部反转后返回false return false;
}int cmp(const void *a,const void *b)
{return int(*(char *)a - *(char *)b);
}
int main(void)
{char str[] bac;int num 1;qsort(str , strlen(str),sizeof(char),cmp);do{printf(第%d个排列\t%s\n,num,str); }while(Next_permutation(str));return 0;
}至此我们已经运用了递归与非递归的方法解决了全排列问题总结一下就是 1、全排列就是从第一个数字起每个数分别与它后面的数字交换。 2、去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。 3、全排列的非递归就是由后向前找替换数和替换点然后由后向前找第一个比替换数大的数与替换数交换最后颠倒替换点后的所有数据。 二、字符串的组合 题目输入一个字符串输出该字符串中字符的所有组合。举个例子如果输入abc它的组合有a、b、c、ab、ac、bc、abc。
上面我们详细讨论了如何用递归的思路求字符串的排列。同样本题也可以用递归的思路来求字符串的组合。 假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符我们有两种选择第一是把这个字符放到组合中去接下来我们需要在剩下的n-1个字符中选取m-1个字符第二是不把这个字符放到组合中去接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码#includeiostream
#includevector
#includecstring
using namespace std;
#includeassert.hvoid Combination(char *string ,int number,vectorchar result);void Combination(char *string)
{assert(string ! NULL);vectorchar result;int i , length strlen(string);for(i 1 ; i length ; i)Combination(string , i ,result);
}void Combination(char *string ,int number , vectorchar result)
{assert(string ! NULL);if(number 0){static int num 1;printf(第%d个组合\t,num);vectorchar::iterator iter result.begin();for( ; iter ! result.end() ; iter)printf(%c,*iter);printf(\n);return ;}if(*string \0)return ;result.push_back(*string);Combination(string 1 , number - 1 , result);result.pop_back();Combination(string 1 , number , result);
}int main(void)
{char str[] abc;Combination(str);return 0;
}由于组合可以是1个字符的组合2个字符的字符……一直到n个字符的组合因此在函数void Combination(char* string)我们需要一个for循环。另外我们用一个vector来存放选择放进组合里的字符。方法二用位运算来实现求组合 #includeiostream
using namespace std;int a[] {1,3,5,4,6};
char str[] abcde;void print_subset(int n , int s)
{printf({);for(int i 0 ; i n ; i){if( s(1i) ) // 判断s的二进制中哪些位为1即代表取某一位printf(%c ,str[i]); //或者a[i]}printf(}\n);
}void subset(int n)
{for(int i 0 ; i (1n) ; i){print_subset(n,i);}
}int main(void)
{subset(5);return 0;
}字符串全排列扩展----八皇后问题题目在8×8的国际象棋上摆放八个皇后使其不能相互攻击即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后这就是一种符合条件的摆放方法。请求出总共有多少种摆法。这就是有名的八皇后问题。解决这个问题通常需要用递归而递归对编程能力的要求比较高。因此有不少面试官青睐这个题目用来考察应聘者的分析复杂问题的能力以及编程的能力。由于八个皇后的任意两个不能处在同一行那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8]数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上也就是数组的两个下标i和j是不是i-jColumnIndex[i]-Column[j]或者j-iColumnIndex[i]-ColumnIndex[j]。关于排列的详细讨论详见上面的讲解。
接下来就是写代码了。思路想清楚之后编码并不是很难的事情。下面是一段参考代码#includeiostream
using namespace std;int g_number 0;
void Permutation(int * , int , int );
void Print(int * , int );void EightQueen( )
{const int queens 8;int ColumnIndex[queens];for(int i 0 ; i queens ; i)ColumnIndex[i] i; //初始化Permutation(ColumnIndex , queens , 0);
}bool Check(int ColumnIndex[] , int length)
{int i,j;for(i 0 ; i length; i){for(j i 1 ; j length; j){if( i - j ColumnIndex[i] - ColumnIndex[j] || j - i ColumnIndex[i] - ColumnIndex[j]) //在正、副对角线上return false;}}return true;
}
void Permutation(int ColumnIndex[] , int length , int index)
{if(index length){if( Check(ColumnIndex , length) ) //检测棋盘当前的状态是否合法{g_number;Print(ColumnIndex , length);}}else{for(int i index ; i length; i) //全排列{swap(ColumnIndex[index] , ColumnIndex[i]);Permutation(ColumnIndex , length , index 1);swap(ColumnIndex[index] , ColumnIndex[i]);}}
}void Print(int ColumnIndex[] , int length)
{printf(%d\n,g_number);for(int i 0 ; i length; i)printf(%d ,ColumnIndex[i]);printf(\n);
}int main(void)
{EightQueen();return 0;
}转载http://zhedahht.blog.163.co题目输入两个整数n和m从数列1,2,3...n中随意取几个数使其和等于m要求列出所有的组合。
#include iostream
#include list
using namespace std;
listint list1;
void find_factor(int sum,int n)
{//递归出口if(n0||sum0)return;//输出找到的数if(sumn){list1.reverse();for(listint::iterator iterlist1.begin();iter!list1.end();iter)cout*iter;coutnendl;list1.reverse();}list1.push_front(n);find_factor(sum-n,n-1);//n放在里面list1.pop_front();find_factor(sum,n-1);//n不放在里面
}int main(void)
{int sum,n;cinsumn;cout所有可能的序列如下endl;find_factor(sum,n);return 0;
}
