字符串的全排列

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

分析：把复杂的问题进行分解，变成更小的问题。分治法一般很容易想到用递归。

首先理解递归：参见http://www.cnblogs.com/zhangqqqf/archive/2008/09/12/1289730.html

递归算法有四个特性：
     必须有可达到的终止条件，否则程序陷入死循环（结合本题，本题终止条件是？这一点很重要）
     子问题在规模上比原问题小
     子问题可通过再次递归调用求解
     子问题的解应能组合成整个问题的解

通过找规律，求字符串的全排列，可以看出三步：

首先，求所有可能出现在第一个位置的字符，

其次，把第一个字符和其后面的字符一一交换。如下图所示，分别把第一个字符a和后面的b、c等字符交换的情形。

接着，固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换

下面的递归的图示意图：

代码结合上面的示意图看就非常清晰了：

#include<iostream>
using namespace std;
#include<assert.h>

void Permutation(char *pStr,char *pbegin)
{
    assert(pStr&&pbegin);

    if (*pbegin == '\0')                                               //*pbegin表示指向当前我们做排列操作的字符串的第一个字符
        printf("%s \n", *pStr);
    else
    {
        for (char *pCh = pbegin; *pCh != '\0'; ++pCh)                  //循环作用就是让每个点都与第一个点作交换
        {
            swap(*pCh, *pbegin);                                       //将每个点与第一个点 *pbegin进行交换
            Permutation(pStr, pbegin + 1);                             //递归，当后面的所有排序都排好了，我们只需要将第一个点与后面所有的结点交换就行了。
            swap(*pCh, *pbegin);                                       //交换后，为了下一次（也就是上面for循环）的交换，我们要把最开始的第一个结点还原。
        }
    }
}

扩展1---去重

当字符串有字符是重复，那么显然我们会打印出重复的字符，怎么解决呢？

全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

增加代码：

#include<iostream>
using namespace std;
#include<assert.h>

//在[nBegin,nEnd)区间中是否有字符与下标为pEnd的字符相等
bool IsSwap(char* pBegin , char* pEnd)
{
    char *p;
    for(p = pBegin ; p < pEnd ; p++)
    {
        if(*p == *pEnd)
            return false;
    }
    return true;
}
void Permutation(char* pStr , char *pBegin)
{
    assert(pStr);

    if(*pBegin == '\0')
    {
        static int num = 1;  //局部静态变量，用来统计全排列的个数
        printf("第%d个排列\t%s\n",num++,pStr);
    }
    else
    {
        for(char *pCh = pBegin; *pCh != '\0'; pCh++)   //第pBegin个数分别与它后面的数字交换就能得到新的排列   
        {
            if(IsSwap(pBegin , pCh))
            {
                swap(*pBegin , *pCh);
                Permutation(pStr , pBegin + 1);
                swap(*pBegin , *pCh);
            }
        }
    }
}

int main(void)
{
    char str[] = "baa";
    Permutation(str , str);
    return 0;
}

扩展2---八皇后问题

分析：为了简化问题，我们这么分析，由于8皇后的任意两个不能处于同一行，那么也就是每一行对应一个皇后，找我们可以定义一个数组：ColumnIndex[8]={0,1,2,3，4,5,6,7}，其中第i个元素对应的是第i行所对应的列。这样一来，由于里面的8个数字是不相同的，所以对应的列也不相同，那么剩下的就是要排除不在同一对角线上的皇后了，也就是：i-j=ColumnIndex[i]-ColumnIndex[j]和j-i=ColumnIndex[i]-ColumnIndex[j]

这其实就是一个全排列问题，排除违反条件下所有的情况。

结论：如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字的所有排列，然后再一一判断每个排列是不是满足题目要求。

代码与扩展一---去重类似：如下：

#include<iostream>
using namespace std;

int g_number = 0;
void Permutation(int * , int  , int );
void Print(int * , int );

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

bool Check(int ColumnIndex[] , int length)
{
    int i,j;
    for(i = 0 ; i < length; ++i)
    {
        for(j = i + 1 ; j < length; ++j)
        {
            if( i - j == ColumnIndex[i] - ColumnIndex[j] || j - i == ColumnIndex[i] - ColumnIndex[j])   //在正、副对角线上
                return false;
        }
    }
    return true;
}
void Permutation(int ColumnIndex[] , int length , int index)
{
    
  //终止条件
if(index == length)
    {
        if( Check(ColumnIndex , length) )   //检测棋盘当前的状态是否合法---违反条件
        {
            ++g_number;
            Print(ColumnIndex , length);
        }
    }
    else
    {
        for(int i = index ; i < length; ++i)   //全排列问题都这么处理
        {
            swap(ColumnIndex[index] , ColumnIndex[i]);
            Permutation(ColumnIndex , length , index + 1);
            swap(ColumnIndex[index] , ColumnIndex[i]);
        }
    }
}

void Print(int ColumnIndex[] , int length)
{
    printf("%d\n",g_number);
    for(int i = 0 ; i < length; ++i)
        printf("%d ",ColumnIndex[i]);
    printf("\n");
}

int main(void)
{
    EightQueen();
    return 0;
}

参考：http://blog.csdn.net/hackbuteer1/article/details/7462447

字符串的全排列

推荐阅读