首页 > 试题广场 > 给出一个函数来输出一个字符串的所有排列。
[问答题]
给出一个函数来输出一个字符串的所有排列。
推荐

题目描述

输入一个字符串,打印出该字符串中字符的所有排列。

例如输入字符串abc,则输出由字符a、b、c 所能排列出来的所有字符串

abc、acb、bac、bca、cab 和 cba。

分析与解法

解法一、递归实现

从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。以对字符串abc进行全排列为例,我们可以这么做:以abc为例

  • 固定a,求后面bc的排列:abc,acb,求好后,a和b交换,得到bac
  • 固定b,求后面ac的排列:bac,bca,求好后,c放到第一位置,得到cba
  • 固定c,求后面ba的排列:cba,cab。
代码可如下编写所示:
void CalcAllPermutation(char* perm, int from, int to)
{
    if (to <= 1)
    {
        return; //递归出口
    }

    if (from == to) //输出条件
    {
        for (int i = 0; i <= to; i++)
            cout << perm[i];
        cout << endl;
    }
    else
    {
        for (int j = from; j <= to; j++)
        {
            swap(perm[j], perm[from]);  //关键
            CalcAllPermutation(perm, from + 1, to);
            swap(perm[j], perm[from]);
        }
    }
}

解法二、字典序排列

首先,咱们得清楚什么是字典序。根据维基百科的定义:给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔集 A × B,则字典序定义为

(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′)。

所以给定两个字符串,逐个字符比较,那么先出现较小字符的那个串字典顺序小,如果字符一直相等,较短的串字典顺序小。例如:abc < abcd < abde < afab。

那有没有这样的算法,使得

  • 起点: 字典序最小的排列, 1-n , 例如12345
  • 终点: 字典序最大的排列,n-1, 例如54321
  • 过程: 从当前排列生成字典序刚好比它大的下一个排列

答案是肯定的:有,即是STL中的next_permutation算法。

在了解next_permutation算法是怎么一个过程之前,咱们得先来分析下“下一个排列”的性质。

  • 假定现有字符串(A)x(B),它的下一个排列是:(A)y(B’),其中A、B和B’是“字符串”(可能为空),x和y是“字符”,前缀相同,都是A,且一定有y > x。
  • 那么,为使下一个排列字典顺序尽可能小,必有:
    • A尽可能长
    • y尽可能小
    • B’里的字符按由小到大递增排列

现在的问题是:找到x和y。怎么找到呢?咱们来看一个例子。

比如说,现在我们要找21543的下一个排列,我们可以从左至右逐个扫描每个数,看哪个能增大(至于如何判定能增大,是根据如果一个数右面有比它大的数存在,那么这个数就能增大),我们可以看到最后一个能增大的数是:x = 1。

而1应该增大到多少?1能增大到它右面比它大的那一系列数中最小的那个数,即:y = 3,故此时21543的下一个排列应该变为23xxx,显然 xxx(对应之前的B’)应由小到大排,于是我们最终找到比“21543”大,但字典顺序尽量小的23145,找到的23145刚好比21543大。

由这个例子可以得出next_permutation算法流程为:

next_permutation算法

  • 定义

    • 升序:相邻两个位置ai < ai+1,ai 称作该升序的首位
  • 步骤(二找、一交换、一翻转)

    • 找到排列中最后(最右)一个升序的首位位置i,x = ai
    • 找到排列中第i位右边最后一个比ai 大的位置j,y = aj
    • 交换x,y
    • 把第(i+ 1)位到最后的部分翻转

还是拿上面的21543举例,那么,应用next_permutation算法的过程如下:

  • x = 1;
  • y = 3
  • 1和3交换
    • 得23541
  • 翻转541
    • 得23145
23145即为所求的21543的下一个排列。参考实现代码如下:
bool CalcAllPermutation(char* perm, int num){
    int i;

    //①找到排列中最后(最右)一个升序的首位位置i,x = ai
    for (i = num - 2; (i >= 0) && (perm[i] >= perm[i + 1]); --i){
        ;
    }
    // 已经找到所有排列
    if (i < 0){
        return false;
    }

    int k;
    //②找到排列中第i位右边最后一个比ai 大的位置j,y = aj
    for (k = num - 1; (k > i) && (perm[k] <= perm[i]); --k){
        ;
    }

    //③交换x,y
    swap(perm[i], perm[k]);
    //④把第(i+ 1)位到最后的部分翻转
    reverse(perm + i + 1, perm + num);
    return true;
}

然后在主函数里循环判断和调用calcAllPermutation函数输出全排列即可。

解法总结

由于全排列总共有n!种排列情况,所以不论解法一中的递归方法,还是上述解法二的字典序排列方法,这两种方法的时间复杂度都为O(n!)。

参考文献:
http://taop.marchtea.com/01.06.html
http://zhedahht.blog.163.com/blog/static/254111742007499363479/
编辑于 2015-02-07 15:10:32 回复(0)
vector<string> ans;
void dfs(string input,string path){

    if(input.size() == 0){
        //到达目标状态
        ans.push_back(path);
    } else{
        //将input中的每一个字母作为第一个字符试一下
        for(int i = 0; i < input.size();i++){
            //不为目标状态,减少字符串最后的一个字符
            string curPath = path;
            curPath += input[i];
            string subtr = input.substr(0,i) + input.substr(i+1);
            dfs(subtr,curPath);
        }
    }
}
int main(){

    string input;
    while(cin >> input){
        dfs(input,"");
        for(auto ele: ans){
            cout<<":"<<ele<<endl;
        }
    }
    return 0;
}

使用递归

发表于 2019-08-03 22:29:19 回复(0)

void pailie(char *str ,char *start) {  if(str== NULL || start==NULL)  {   return ;  }  if(*start == '\0')  {   printf("%c\n",str);  }  else  {      char *pch;   char tmp;   for(pch = start ; pch != '\0' ;pch++)   {    tmp = *pch;    *pch = *start;    *start = tmp;

   pailie(str , start+1);        tmp = *pch ;    *pch = *start;    *start = tmp;   }  } } void main() {  char *str="abc";  char *start = str;  pailie(str ,str); }


发表于 2015-01-26 19:36:16 回复(1)