字符排列组合

对于字符排列组合的认知一直很模糊,曾经花了比较多的时间去试图搞清楚,过了一段时间,却还是忘得厉害,不懂从哪里下手解决.比如之前花很多时间看的问题:
输入一个字符串,输出该字符串的全排列.
今天完全想不起来当时是怎么理解的了,看来还是要写下来.只有能写清楚了,才说明自己真的理解了.

Quote

先看看别人怎么解释这个问题的.摘转Hackbuteer1的专栏的部分说明:

全排列的递归实现
为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了：

或许我的理解力有限,看了半天也无法明白.后来自己尝试从数学的角度来看待:
数学上,求一个n个长度的字符串的全排列的总数,首先第1位可以有n种可能,第2位有n-1种可能,...,第n位有1种可能.总数为n的阶乘.
程序的设计上也可以采用类似的方法:

先将所有可能的字符取一个放在第1位.
将剩下的字符取一个放在第2位.
...

Analysis

原理虽是如此,但是实现起来还是需要一点技巧.从这个角度看,昨日写的"字符组合"问题显得更为简单了,因为下一个字符的可能只有两种.但是在今天这个场景中,可能的字符是很多的.那么怎么将所有的可能的字符放到第1位呢?
利用交换.用一个循环把字符串中的字符依次交换到第1位即可.比如说"123",第1位有3个可能:"1","2","3".通过1和1交换,1和2交换,1和3交换,我们就得到了第1位的三种可能:
123,213,312.接下来就要解决第2位的问题.

123 对123来说,1被固定了,第二位只有两种情况:2和3.因此理应得到"123"和"132"的组合.同样是利用交换,2和2交换得到123,2和3交换得到132.
213 同理,最终得到213和231
312 最终得到312和321.

由于确定了前两位,第三位只有一个选择,因此也在前面的步骤中被固定了.不需要再次进行考虑,需要做的只是第3位和第3位自身进行交换而已.

从前面的分析可以看出,问题模式一样,且规模变小.可以利用递归进行解决.递归基就是"当前考虑的是第n+1位时".原因是n+1位是结束符'\0'.

Implementation

void Permutation(char* pStr,char* pBegin)
{
    assert(pStr&&pBegin);
    if(*pBegin=='\0')
    {
        printf("%s\n",pStr);
        return;
    }
    else
    {
        for(char* it=pBegin;it!='\0';it++)
        {
            swap(*it,*pBegin);  //当前位和后面的字符依次交换,如123,1和2交换得到213
            Permutation(*pStr,pBegin+1);
            swap(*it,*pBegin);  //213还原为123,以便下次迭代能得到321.
        }
    }
}

Duplicate Removal

更进一步,还需要考虑去重的问题。比如当输入122时，用上面的方法是不对的，会输出一些重复的数值。直观的去重方法是：
比较即将要交换的两个字符，如果相等则不进行交换。还是拿122来说，第1位与各位交换后，可以得到122,212和221。（其实这里要得到122，也还需要做额外的处理，因为1和自身是相等的，按照规则不会进行处理).对第二位的各个情况：

122 2和2相等，不进行交换。只会输出122.
212 输出212和221.
221 输出221和212.

可以看到，这个规则并不能得到预期的结果。原因在于，虽然1和后面两个2不等，但是交换之后，得到的数的后两位都是包含了1和2，虽然顺序不同（212和221）,但是进入深层的递归之后，交换得到的数是一样的。
转换一种思路：
当两个字符即将进行交换时，搜索当前字符之前的所有字符，如果有字符和当前字符相等。则表明不需要进行交换。比如准备交换122中的1和第2个'2'时，搜索发现，第2个'2'之前有字符和'2'相等，这表示如果还继续交换的话，未来将引入重复的值。

Implementation Version2

bool IsSwap(char* pBegin,char* pEnd)
{
    for(char* it=pBegin;it<pEnd;it++)
    {
        if(*it==*pEnd)
            return false;
    }
    return true;
}
void PermutationVer2(char* pStr,char* pBegin)
{
    assert(pStr&&pBegin);
    if(*pBegin=='\0')
    {
        printf("%s\n",pStr);
        return;
    }
    else
    {
        for(char* it=pBegin;it!='\0';it++)
        {
            if(IsSwap(pBegin,it))
            {
                swap(*it,*pBegin);  //当前位和后面的字符依次交换,如123,1和2交换得到213
                Permutation(*pStr,pBegin+1);
                swap(*it,*pBegin);  //213还原为123,以便下次迭代能得到321.
            }
        }
    }
}

Combination

组合问题要求输出集合中所有可能的组合.如"123"输出

    {}
    {3 }
    {2 }
    {3 2 }
    {1 }
    {3 1 }
    {2 1 }
    {3 2 1 }

优雅的思路是用位运算求解.一个长度为n的字符串,每一位上的字母或者取或者不取,因此一共有2^n种可能组合.
这2^n种组合,对应到二进制0->(2^n-1),这n个数,某一位上的1代表取该位的字符,0则相反.
因此我们只要从0循环到2^n-1,每次查看当前的数字,输出为1的数位上对应的字符即可.

Implementation of Combination

/*
 * 输入一个集合,输出该集合的组合
 */

#include <cstdio>
#include<cstring>
using namespace std;

void Print(char* str,int current)
{
    printf("{");
    for(int i=0;i<strlen(str);i++)
    {
        if(current&(1<<i))     //通过循环查看current中哪几位是1
            printf("%c ", str[strlen(str)-i-1]);  //对为1的位进行输出
    }
    printf("}\n");
}

int main()
{
    char str[]="123";
    for(int i=0;i<(1<<strlen(str));i++)
    {
        Print(str,i);
    }
    return 0;
}

Extension

求两个字符串的组合,且字符要保持在源字符串的顺序. 参阅另一篇博文字母组合问题

八皇后问题用长度为8的数组columnIndex存储位置信息.columnIndex[i]=j表示第i行的皇后放置在第j列.用0->7对数组进行初始化,就保证了各行的皇后不会在同一列上.现在的问题就转换为"01234567"的全排列问题.
在产生一个排列后,我们只需再判断有没有某两个皇后在同一斜线上就可以了,在斜线上的皇后,有行列号有以下规律:

columnIndex[i]-columnIndex[j]==i-j 或者 columnIndex[i]-columnIndex[j]==j-i

代码如下:

/*用全排列解决八皇后问题 */
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int total=0;
int columnIndex[8];

bool IsCheck()
{
    for(int i=0;i<8;i++)
    {
        for(int j=i+1;j<8;j++)
        {
            if(columnIndex[i]-columnIndex[j]==i-j||columnIndex[i]-columnIndex[j]==j-i)
                return false;
        }
    }
    return true;
}
void Print()
{
    printf("%d\n", total);
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            if(j==columnIndex[i])
                printf("X ");
            else
                printf("O ");
        }
        printf("\n");
    }
} 
void Permutation(int current)
{
    if(current==8)
    {
        if(IsCheck())
        {
            total++;
            Print();
        }
    }
    else 
    {
        for(int i=current;i<8;i++)
        {
            swap(columnIndex[current],columnIndex[i]);
            Permutation(current+1);
            swap(columnIndex[current],columnIndex[i]);
        }
    }
}

void Solution()
{
    for(int i=0;i<8;i++)
        columnIndex[i]=i;
    Permutation(0);
}
int main()
{
    Solution();
    return 0;
}

PS:
这种全排列求解八皇后问题的方法不是最快的,因为生成了很多不合格的方案,最后又进行筛选,时间效率上有一定的损失.更多的解法可以去看N皇后问题的两个最高效的算法

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