题目描述：
-
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
- 输入：
-
每个测试案例包括1行。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
- 输出：
-
对应每组数据,按字典序输出所有排列。
- 样例输入：
abc
BCA
- 样例输出：
abc
acb
bac
bca
cab
cba
ABC
ACB
BAC
BCA
CAB
CBA
解题思路：
这道题要注意两个问题：
第一个是重复字母，第二个是按字典顺序。
重复字母我们在进行交换的时候直接跳过就可以了，按字典顺序，这个就需要我们进行排列了。
排列使用冒泡排序：
void bubbleSort(char *arr,int begin,int length){
int i,j;
for(i=begin;i<length;i++){
for(j=i+;j<length;j++){
if(arr[i]>arr[j]){
swap(&arr[i],&arr[j]);
}
}
}
}
进行交换时，注意忽略掉重复的字符交换：
void Permulation(char *arr,int k,int length){
int i;
if(k == length){
for(i=;i<length;i++)
printf("%c",arr[i]);
printf("\n");
}else{
for(i=k;i<length;i++){
if(k != i && arr[k] == arr[i])
continue;
swap(&arr[k],&arr[i]);
bubbleSort(arr,k+,length);
Permulation(arr,k+,length);
bubbleSort(arr,k+,length);
}
}
}
每次在进行交换后，都把剩余的元素进行一次排列。比如字符串abc,在进行最后一次外层交换时变成 cba。
此时要进行一次排序，交换cab后，在进行排列。
全部代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bubbleSort(char *arr,int begin,int length);
void swap(char *a,char *b);
void Permulation(char *arr,int k,int length); int main(){
char arr[];
int length;
int i;
while(gets(arr)){
length = strlen(arr);
bubbleSort(arr,,length);
Permulation(arr,,length);
}
return ;
}
void Permulation(char *arr,int k,int length){
int i;
if(k == length){
for(i=;i<length;i++)
printf("%c",arr[i]);
printf("\n");
}else{
for(i=k;i<length;i++){
if(k != i && arr[k] == arr[i])
continue;
swap(&arr[k],&arr[i]);
bubbleSort(arr,k+,length);
Permulation(arr,k+,length);
bubbleSort(arr,k+,length);
}
}
}
void swap(char *a,char *b){
char c;
c = *b;
*b = *a;
*a = c;
}
void bubbleSort(char *arr,int begin,int length){
int i,j;
for(i=begin;i<length;i++){
for(j=i+;j<length;j++){
if(arr[i]>arr[j]){
swap(&arr[i],&arr[j]);
}
}
}
}
/**************************************************************
Problem: 1369
User: xhalo
Language: C
Result: Accepted
Time:470 ms
Memory:912 kb
****************************************************************/