Posted on 2012-11-05 21:01
鑫龍 閱讀(399)
評論(0) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)與算法
第十六章、全排列問題
53.字符串的排列。
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c 所能排列出來的所有字符串
abc、acb、bac、bca、cab 和cba。
分析：此題最初整理于去年的微軟面試100題中第53題，第二次整理于微軟、Google等公司非常好的面試題及解答[第61-70題] 第67題。無獨(dú)有偶，這個(gè)問題今年又出現(xiàn)于今年的2011.10.09百度筆試題中。ok，接下來，咱們先好好分析這個(gè)問題。
- 一、遞歸實(shí)現(xiàn)
從集合中依次選出每一個(gè)元素，作為排列的第一個(gè)元素，然后對剩余的元素進(jìn)行全排列，如此遞歸處理，從而得到所有元素的全排列。以對字符串a(chǎn)bc進(jìn)行全排列為例，我們可以這么做：以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;
- }
- }
- }
- 二、字典序排列
把升序的排列（當(dāng)然，也可以實(shí)現(xiàn)為降序）作為當(dāng)前排列開始，然后依次計(jì)算當(dāng)前排列的下一個(gè)字典序排列。
對當(dāng)前排列從后向前掃描，找到一對為升序的相鄰元素，記為i和j（i < j）。如果不存在這樣一對為升序的相鄰元素，則所有排列均已找到，算法結(jié)束；否則，重新對當(dāng)前排列從后向前掃描，找到第一個(gè)大于i的元素k，交換i和k，然后對從j開始到結(jié)束的子序列反轉(zhuǎn)，則此時(shí)得到的新排列就為下一個(gè)字典序排列。這種方式實(shí)現(xiàn)得到的所有排列是按字典序有序的，這也是C++ STL算法next_permutation的思想。算法實(shí)現(xiàn)如下：
- 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; // 已經(jīng)找到所有排列
-
- 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);
-
- }
- }