排列与组合
问题描述：
对一个字符串，求出其所有的全排列情况和所有的组合情况。
例如字符串 abc
其所有的全排列是 abc, acb, bac, bca, cab, cba
其所有的组合是：a, b, c, ab, ac, bc, abc
全排列：
固定前面的元素，对后面的进行递归求解，求解后，恢复之前的状态，并将后面的元素与前面的进行交换。
代码描述：
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;
}
}
}
组合：
对于组合，也是从头扫描字符串的第一个元素，按照数学上的公式，对于第一个元素有两种选择，一是取该元素，然后再剩下来的 n - 1 个元素中取 m - 1 个；而是不去该元素，然后在 n - 1 个元素中取 m 个元素。
C(m, n) = C(m - 1, n - 1) + C(m, n - 1)
这两种选择都可以进一步递归求解。
代码描述：
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 阅读(112)
评论(0) 编辑 收藏 引用