排列與組合
問題描述：
對(duì)一個(gè)字符串，求出其所有的全排列情況和所有的組合情況。
例如字符串 abc
其所有的全排列是 abc, acb, bac, bca, cab, cba
其所有的組合是：a, b, c, ab, ac, bc, abc
全排列：
固定前面的元素，對(duì)后面的進(jìn)行遞歸求解，求解后，恢復(fù)之前的狀態(tài)，并將后面的元素與前面的進(jìn)行交換。
代碼描述：
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;
}
}
}
組合：
對(duì)于組合，也是從頭掃描字符串的第一個(gè)元素，按照數(shù)學(xué)上的公式，對(duì)于第一個(gè)元素有兩種選擇，一是取該元素，然后再剩下來的 n - 1 個(gè)元素中取 m - 1 個(gè)；而是不去該元素，然后在 n - 1 個(gè)元素中取 m 個(gè)元素。
C(m, n) = C(m - 1, n - 1) + C(m, n - 1)
這兩種選擇都可以進(jìn)一步遞歸求解。
代碼描述：
void Combination(char* string)
{
if(string == NULL)
return;
int length = strlen(string);
vector<char> result;
for(int i = 1; i <= length; ++ i)
{
Combination(string, i, result);
}
}
void Combination(char* string, int number, vector<char>& result)
{
if(number == 0)
{
vector<char>::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);
}
參考：
字符串的排列
http://zhedahht.blog.163.com/blog/static/254111742007499363479/
字符串的組合
http://zhedahht.blog.163.com/blog/static/2541117420114172812217/
posted on 2011-09-17 09:54
unixfy 閱讀(114)
評(píng)論(0) 編輯 收藏 引用