字符串的全排列和组合算法（扩展：八皇后问题）_字符串排列组合算法

一、字符串的全排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a,b,c所能排列出来的所有字符串abc，acb,bac,bca,cab,cba。

算法思想：
我们现在来看这个例子，分为如下三组：

a b c——a c b

b a c——b c a

c b a——c a b

我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面的所有字符交换。第二步固定第一个字符，求后面所有字符的全排列，分析到这里，我们很容易就可以看出这是一个典型的递归思路。

第一步：

先 将a b c中的a和b交换得到b a c

将a b c中的a和c交换得到c b a

第二步：

将a b c中的b和c交换得到a c b

将b a c中的a和c交换得到b c a

将c b a中的b和a交换得到c a b

递归代码如下：

#include<iostream>
using namespace std;

void Permutation(char* pStr,char* pBegin)
{
   if(pStr==NULL && pBegin==NULL)
   {
       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;
       }
   }
}

int main()
{
    char str[]="abc";
    Permutation(str,str);
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

下面我们来考虑一下：如果字符串中有重复的字符的话，怎么去掉重复的字符呢？

我们第一种方法给出的全排列思路就是从第一个数字起每个数字分别与它后面的数字交换。我们可以这样假设，如果一个数与后面的数字相同则这两个数就不交换了。比如1 3 3，第一个数字与后面交换得到3 1 3，然后第二个数与第三个数因为两个相等就不用交换了。但是对3 1 3，第二个数与第三个数是不相等的，所以交换得到3 3 1，这与1 3 3中第一个数与第三个数交换所得的3 3 1重复了，所以该方案不可行。

下面我们换一种思路：对于1 3 3，第一个数与第二个数交换得到3 1 3.然后考虑第一个数与第三个数交换，此时由于第二个数与第三个数相等，所以第一个数不再与第三个数交换。下面考虑3 1 3，第二个数与第三个数交换得到3 3 1，此时所有的全排列生成完毕。

所以，去掉重复的规则就是：从第一个数字起每个数字与它后面非重复出现的数字交换

#include<iostream>
using namespace std;

bool IsSwap(char* pBegin,char* pEnd)
{
    for(char* p=pBegin;p<pEnd;p++)
    {
        if(*p==*pEnd)
        {
           return false;
        }
    }
    return true;
}


void Permutation(char* pStr,char* pBegin)
{
    if(pStr==NULL && pBegin==NULL)
    {
        return;
    }
    if(*pBegin=='\0')
    {
        static int num=1;
        printf("%s\n第%d个排列\n",pStr,num++);
    }
    else{
        for(char* pCh=pBegin;*pCh!='\0';pCh++)
        {
            if(IsSwap(pBegin,pCh))
            {
               char temp=*pCh;
               *pCh=*pBegin;
               *pBegin=temp;
               Permutation(pStr,pBegin+1);
               char temp=*pCh;
               *pCh=*pBegin;
               *pBegin=temp;
            }
        }
    }
}

int main()
{
   char str[]="baa";
   Permutation(str,str);
   system("pasue");
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

二、字符串的组合

题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a,b,c,ab,ac,bc,abc

我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：

1.把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符。

2.不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

//从头扫描字符串得到第一个字符，针对第一个字符，有两种选择
//把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符
//如果不把这个字符放到组合中去，则需要在剩下的n-1个字符中选取m个字符

void Combination(char* string,int number,vector<char> &result)
{
    if(number==0)//直接打印出组合中的字符
    {
       static int num=1;
       printf("第%d个组合\n",num++);
       vector<char>::iterator iter=result.begin();
       for(;iter!=result.end();++iter)
       {
           printf("%c",*iter);
       }
       printf("\n");
       return;
    }
    result.push_back(*string);
    Combination(string+1,number-1,result);//把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符
    result.pop_back();
    Combination(string+1,number,result);//不把这个字符放到组合中去，则接下来我们需要在剩下的n-1个字符中选取m个字符
}

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);
    }
}

int main(void)  
{  
    char str[] = "abc";  
    Combination(str);  
    system("pause");
    return 0;  
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

上面递归代码看着很简单，但其实并不容易理解，建议大家自己动手模拟一下组合的操作。这样可以加深自己对代码的理解。

三、八皇后问题

题目：在8*8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行，同一列或者同一对角线上。下图中的每个黑色格子表示一个皇后，这就是一种复合条件的摆放问题，请求出总共有多少种摆法。

思路：由于八个皇后的任意两个不能在同一行，那么一定是每个皇后占据一行。那么我们可以定义一个数组Column[8]，数组中第 i个数字表示位于第 i行的皇后所在的列号。我们将这Column[8]用0-7初始化。然后对该数组进行全排列。因为初始化时 每个值都不同，所以这8个皇后肯定在不同列。接下来我们只需要判断得到的每一个排列对应的八个皇后是不是在同一个对角斜线上，即数组的两个下标i和j，是不是i-j==Column[i]-Column[j]或者j-i==Column[i]-Column[j]

代码如下：

#include<iostream>
using namespace std;

int number=0;//计数

bool Judge(int Column[],int length)
{
    for(int i=0;i<length;++i)
    {
        for(int j=i+1;j<length;++j)
        {
            if(i-j==Column[i]-Column[j] || j-i==Column[i]-Column[j])
            {
                return false;
            }
        }
    }
    return true;
}

void Permutation(int Column[],int length,int index)
{
   if(index==length)
   {
      if(Judge(Column,length))//检测棋盘状态是否合法
      {
         //状态合法，打印出全排列结果
         ++number;
         printf("%d\n",number);
         for(int i=0;i<length;++i)
         {
             printf("%d",Column[i]);
         }
         printf("\n");
      }
   }
   else
   {
       for(int i=index;i<length;++i)
       {
          swap(Column[index],Column[i]);
          Permutation(Column,length,index+1);
          swap(Column[index],Column[i]);
       }
   }
}

void EightQueen()
{
    const int queens=8;
    int Column[queens];
    //先初始化列号
    for(int i=0;i<queens;++i)
    {
        Column[i]=i;
    }
    Permutation(Column,queens,0);

}

int main()
{
   EightQueen();
   system("pause");
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

总共92中放置方法！

四：组合问题拓展：

题目：输入两个整数n和m，从数列1,2,3…..n 中随意取几个数，使其和等于m，要求列出所有的组合。

算大思想：这个问题其实就是组合问题的延伸。

1、我们首先判断传入进来的两个整数是否相等，若相等，则是其中一种解法。

2、若传入进来的两数不相等，则先将n放入到容器中，对剩下的(n-1)个数判断和是不是等于(sum-n)。这很明显的利用了递归的思想。

3.当对第二步递归结束以后发现找不到合适的解的话就将n从容器中删除，对剩下的（n-1）个数利用递归方法判断是否等于sum

了解了算法思想以后，代码就很容易实现了：

#include<iostream>
#include<vector>

using namespace std;
vector<int> ivec1;

void find_Combination(int sum,int n)
{
   if(n<=0||sum<=0)
   {
      return;
   }
   if(sum==n)
   {
      vector<int>::iterator iter=ivec1.begin();
      for(;iter!=ivec1.end();++iter)
      {
         cout<<*iter<<"+";
      }
      cout<<n<<endl;
   }
   ivec1.push_back(n);
   find_Combination(sum-n,n-1);
   ivec1.pop_back();
   find_Combination(sum,n-1);
}

int main()
{
   int sum,n;
   cin>>sum>>n;
   cout<<"所有可能的序列如下："<<endl;
   find_Combination(sum,n);
   system("pause");
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36