首先我們區(qū)分一下排列和組合：
- 輸入一個(gè)字符串管毙，得到這個(gè)字符串的所有組合（不是排列）：
比如輸入abc辆脸，得到a,ab,ac,b,bc,abc,c - 排列：
a(bc),a(cb),b(ac),b(ca),c(ab),c(ba)
組合
把問(wèn)題簡(jiǎn)化為長(zhǎng)度為n的字符串中求m個(gè)字符串的組合求冷。
我可以從第一個(gè)字符開(kāi)始昨忆，有兩種情況：
1隧期，含有這個(gè)字符恰起，然后求剩下m-1個(gè)字符串的組合幌绍；
2颁褂，不含有這個(gè)字符故响，然后求剩下m個(gè)字符串的組合；
a+a(fun(bc))+fun(bc)
fun(bc):
b+bfun(c)+fun(c)
也就是：
b,bc,c
so:
a,a(b,bc,c),(b,bc,c)
和很多字符串的題目一樣颁独，我們使用遞歸的方法：
首先是驅(qū)動(dòng)函數(shù)：
#include <iostream>
#include <vector>
void combination(char* str, int number, std::vector<char>& vec);
void combinate(char* str)
{
if (!str)
return;
size_t len = strlen(str);
std::vector<char> str_vec;
for (int i = 1; i <= len; i++)
{
combination(str, i, str_vec);
}
}
首先我們檢測(cè)輸入是否合法彩届，然后我們從第一個(gè)字符串開(kāi)始，得到關(guān)于當(dāng)前這個(gè)字符和后面字符串（看成一個(gè)整體）的序列誓酒，而后面所有字符的情況只需要遞歸的調(diào)用就好了
void combination(char* str, int number, std::vector<char>& vec)
{
if (number == 0)
{
auto beg = vec.begin();
for (beg; beg!=vec.end(); beg++)
std::cout << *beg;
std::cout << std::endl;
}
if (*str != '\n')
return;
vec.push_back(*str);
combination(str+1, number - 1, vec);
vec.pop_back();
combination(str + 1, number, vec);
}
我們的參數(shù)列表包括字符串的指針樟蠕，當(dāng)前字符的位置number,還有存儲(chǔ)在vector里面的字符（等待打印）靠柑。
這個(gè)函數(shù)就是按照前面的思路寫(xiě)的：
1寨辩，含有這個(gè)字符，然后求剩下m-1個(gè)字符串的組合歼冰；
2靡狞，不含有這個(gè)字符，然后求剩下m個(gè)字符串的組合停巷；
情況1對(duì)應(yīng)：
vec.push_back(*str); combination(str+1, number - 1, vec);
情況2：
vec.pop_back(); combination(str + 1, number, vec);
先把當(dāng)前字符刪除耍攘，然后打印
最后，說(shuō)實(shí)話畔勤，看了這么多遞歸蕾各，感覺(jué)真的寫(xiě)得好，庆揪，可是我就是不會(huì)哈哈哈式曲。。
排列
- 排列：
a(bc),a(cb),b(ac),b(ca),c(ab),c(ba)
這一部分在8皇后問(wèn)題里面已經(jīng)用到過(guò)這個(gè)方法了缸榛；
思路就像上面舉例子寫(xiě)的一樣吝羞，通過(guò)交換位置來(lái)達(dá)到目的。
我們分別把每個(gè)字符放到最開(kāi)始的位置内颗，而剩余的字符使用遞歸的方法來(lái)做同樣的事情钧排。
核心部分：
//偽代碼 swap(*pch,*pbegin); permutation(pbegin+1); swap(*pch,*pbegin);
這個(gè)要遞歸兩遍吧，實(shí)際情況很復(fù)雜的均澳。
void Permutation(char* pStr, char* pBegin)
{
if (!pStr || !pBegin)
return;
// if pBegin points to the end of string,
// this round of permutation is finished,
// print the permuted string
if (*pBegin == '\0')
{
printf("%s\n", pStr);
}
// otherwise, permute string
else
{
for (char* pCh = pBegin; *pCh != '\0'; ++pCh)
{
// swap pCh and pBegin
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
// restore pCh and pBegin
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
文章參考何海濤大神文章
