首页 > 代码库 > 打印给定字符串中字符的所有排列

打印给定字符串中字符的所有排列

2024-07-18 08:20:11   222人阅读

<style></style>

题目：

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

 

解决：

　　简单起见，字符串中没有相同的字符。

　　其实这是个递归的过程：对于字符串str，先分别逮住其中的每一个，如s，把它从str中踢开，成了 s + tr（下一次踢开t变为 t + sr），然后对于剩下来的，再从剩下的再次分别踢开一个加到左边的后面（假想被踢开的都在左边，剩下的都在右边哈），一直如此，直至右边都踢光了。算法如下：　　

void show(strL, strR){    if (strR不是空字符串)    {        for (对于strR中的每一个字符)        {            把这个字符踢到strL的后面            递归show()        }    }     else    {        显示左边的字符串    }}

　　代码如下：

 1 #include <iostream> 2 #include <string> 3  4 using std::cout; 5 using std::endl; 6 using std::cin; 7 using std::string; 8  9 //在这个过程中，把字符串分为左右两半，左边的字符已经固定，右边的可以组合出各种情况10 //最后把左边固定的和右边各种情况一一连接，就是完整的各种字符串了11 void show(string strL, string strR)12 {13     if (!strR.empty())        //右边的非空14     {15         for (int i = 0; i < strR.size(); i++)        //对于每种情况16         {17             //注意要用左右字符串的副本18             string tempL = strL;19             string tempR = strR;20 21             tempL.append(1, strR[i]);        //把那个字符添加到左边字符串的后面22             tempR.erase(i, 1);        //右边的字符串中删除那个23             show(tempL, tempR);        //递归进行24         }25     } 26     else27     {28         cout << strL << endl;29     }30 }31 32 int main(void)33 {34     string left;35     string test("abcde");36 37     show(left, test);38     cout << "------------------------------------\n" << left << endl << test;39 40     cin.get();41 }

 　　结果：

 

总结：

　　递归的思想。

　　其实可以看做一棵树，从根节点开始分叉，每一个分叉是一种情况，最终到叶节点的高度为n，n为字符串长度，每个叶节点是一种情况。


联系
我们