Posted on 2012-11-05 21:01
鑫龙 阅读(378)
评论(0) 编辑 收藏 引用 所属分类:
数据结构与算法
第十六章、全排列问题
53.字符串的排列。
题目:输入一个字符串,打印出该字符串中字符的所有排列。
例如输入字符串abc,则输出由字符a、b、c 所能排列出来的所有字符串
abc、acb、bac、bca、cab 和cba。
分析:此题最初整理于去年的微软面试100题中第53题,第二次整理于微软、Google等公司非常好的面试题及解答[第61-70题] 第67题。无独有偶,这个问题今年又出现于今年的2011.10.09百度笔试题中。ok,接下来,咱们先好好分析这个问题。
- 一、递归实现
从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。以对字符串abc进行全排列为例,我们可以这么做:以abc为例
固定a,求后面bc的排列:abc,acb,求好后,a和b交换,得到bac
固定b,求后面ac的排列:bac,bca,求好后,c放到第一位置,得到cba
固定c,求后面ba的排列:cba,cab。代码可如下编写所示:
- template <typename T>
- void CalcAllPermutation_R(T perm[], int first, int num)
- {
- if (num <= 1) {
- return;
- }
-
- for (int i = first; i < first + num; ++i) {
- swap(perm[i], perm[first]);
- CalcAllPermutation_R(perm, first + 1, num - 1);
- swap(perm[i], perm[first]);
- }
- }
或者如此编写,亦可:
- void Permutation(char* pStr, char* pBegin);
-
- void Permutation(char* pStr)
- {
- Permutation(pStr, pStr);
- }
-
- void Permutation(char* pStr, char* pBegin)
- {
- if(!pStr || !pBegin)
- return;
-
- if(*pBegin == '\0')
- {
- printf("%s\n", pStr);
- }
- else
- {
- for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
- {
-
- char temp = *pCh;
- *pCh = *pBegin;
- *pBegin = temp;
-
- Permutation(pStr, pBegin + 1);
-
- temp = *pCh;
- *pCh = *pBegin;
- *pBegin = temp;
- }
- }
- }
- 二、字典序排列
把升序的排列(当然,也可以实现为降序)作为当前排列开始,然后依次计算当前排列的下一个字典序排列。
对当前排列从后向前扫描,找到一对为升序的相邻元素,记为i和j(i < j)。如果不存在这样一对为升序的相邻元素,则所有排列均已找到,算法结束;否则,重新对当前排列从后向前扫描,找到第一个大于i的元素k,交换i和k,然后对从j开始到结束的子序列反转,则此时得到的新排列就为下一个字典序排列。这种方式实现得到的所有排列是按字典序有序的,这也是C++ STL算法next_permutation的思想。算法实现如下:
- template <typename T>
- void CalcAllPermutation(T perm[], int num)
- {
- if (num < 1)
- return;
-
- while (true) {
- int i;
- for (i = num - 2; i >= 0; --i) {
- if (perm[i] < perm[i + 1])
- break;
- }
-
- if (i < 0)
- break; // 已经找到所有排列
-
- int k;
- for (k = num - 1; k > i; --k) {
- if (perm[k] > perm[i])
- break;
- }
-
- swap(perm[i], perm[k]);
- reverse(perm + i + 1, perm + num);
-
- }
- }