题目1369：字符串的排列

 

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：901

解决：213

题目描述：

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

输入：

每个测试案例包括1行。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

输出：

对应每组数据,按字典序输出所有排列。

 

样例输入：

abcBCA

样例输出：

abcacbbacbcacabcbaABCACBBACBCACABCBA

 

算法分析

         这道题类似 

         题目1251：序列分割，

         题目1377：缓变序列

         本质上都是对原数组进行了排序，是满足一定条件，而这道题只不过是没有条件，列出所有可能排列情况。

         我们利用递归实现，类似DFS.

         added[10]标识字符是否加入排列

         arS[10]保存排列后的结果

        考虑到字符可能有重复，先对字符串进行排序，重复的字符串就相邻挨在一起。在递归时就可以避免重复。

pre保存前一个选择加入的字符

 

if(!added[i]){			if(s[i]!=pre){

        通过比较当前s[i]和Pre可以避免重复。

 

        假定arS已经保存了arN个字符。

 

void arrangeString(std::string &s,int arN){

        我们在s剩下的未加入的字符中，选取下一个加入的字符，并把该字符标记为added[i] = true

 

        再完成一次递归 arrangeString(s,arN+1) 后，记得将added[i]重置为false,更新pre = s[i]

char pre = '\0';	//bool finish = true;	for(int i = j;i

 

源程序

输出用printf("%s\n",arS);不然超时。

 

//============================================================================// Name        : judo1369.cpp// Author      : wdy// Version     :// Copyright   : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;bool added[10] = {false};char arS[10] = "\0";void arrangeString(std::string &s,int arN){	int len = s.size();	int j = 0;	for(j = 0;j
        
         >a;}void judo(){		std::string st;	while(std::cin>>st){		printString(st);	}	}int main() {	//test();	judo();	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!	return 0;}