posts - 200, comments - 8, trackbacks - 0, articles - 0

全排列算法及其C++实现(转)

Posted on 2012-11-05 21:01 鑫龙 阅读(376) 评论(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。代码可如下编写所示：
  1. template <typename T>  
  2. void CalcAllPermutation_R(T perm[], int first, int num)  
  3. {  
  4.     if (num <= 1) {  
  5.         return;  
  6.     }  
  7.       
  8.     for (int i = first; i < first + num; ++i) {  
  9.         swap(perm[i], perm[first]);  
  10.         CalcAllPermutation_R(perm, first + 1, num - 1);  
  11.         swap(perm[i], perm[first]);  
  12.     }  
  13. }  
    或者如此编写，亦可：
  1. void Permutation(char* pStr, char* pBegin);  
  2.   
  3. void Permutation(char* pStr)  
  4. {  
  5.       Permutation(pStr, pStr);  
  6. }  
  7.   
  8. void Permutation(char* pStr, char* pBegin)  
  9. {  
  10.     if(!pStr || !pBegin)  
  11.         return;  
  12.       
  13.     if(*pBegin == '\0')  
  14.     {  
  15.         printf("%s\n", pStr);  
  16.     }  
  17.     else  
  18.     {  
  19.         for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)  
  20.         {  
  21.             // swap pCh and pBegin  
  22.             char temp = *pCh;  
  23.             *pCh = *pBegin;  
  24.             *pBegin = temp;  
  25.               
  26.             Permutation(pStr, pBegin + 1);    
  27.             // restore pCh and pBegin  
  28.             temp = *pCh;  
  29.             *pCh = *pBegin;  
  30.             *pBegin = temp;  
  31.         }  
  32.     }  
  33. }  
  • 二、字典序排列
    把升序的排列（当然，也可以实现为降序）作为当前排列开始，然后依次计算当前排列的下一个字典序排列。
    对当前排列从后向前扫描，找到一对为升序的相邻元素，记为i和j（i < j）。如果不存在这样一对为升序的相邻元素，则所有排列均已找到，算法结束；否则，重新对当前排列从后向前扫描，找到第一个大于i的元素k，交换i和k，然后对从j开始到结束的子序列反转，则此时得到的新排列就为下一个字典序排列。这种方式实现得到的所有排列是按字典序有序的，这也是C++ STL算法next_permutation的思想。算法实现如下：
  1. template <typename T>  
  2. void CalcAllPermutation(T perm[], int num)  
  3. {  
  4.     if (num < 1)  
  5.         return;  
  6.           
  7.     while (true) {  
  8.         int i;  
  9.         for (i = num - 2; i >= 0; --i) {  
  10.             if (perm[i] < perm[i + 1])  
  11.                 break;  
  12.         }  
  13.           
  14.         if (i < 0)  
  15.             break;  // 已经找到所有排列  
  16.       
  17.         int k;  
  18.         for (k = num - 1; k > i; --k) {  
  19.             if (perm[k] > perm[i])  
  20.                 break;  
  21.         }  
  22.           
  23.         swap(perm[i], perm[k]);  
  24.         reverse(perm + i + 1, perm + num);  
  25.          
  26.     }  
  27. }  
  扩展：如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？当输入的字符串中含有相同的字符串时，相同的字符交换位置是不同的排列，但是同一个组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc

转自 http://blog.csdn.net/v_july_v/article/details/6879101


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理