posts - 183,  comments - 10,  trackbacks - 0

排列与组合
问题描述:
对一个字符串,求出其所有的全排列情况和所有的组合情况。
例如字符串 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* stringint 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 阅读(111) 评论(0)  编辑 收藏 引用

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