劍指OFFER之字符串的排列（九度OJ1369）

題目描述：

 

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串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+1;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=0;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+1,length);
            Permulation(arr,k+1,length);
            bubbleSort(arr,k+1,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[10];
    int length;
    int i;
    while(gets(arr)){
        length = strlen(arr);
        bubbleSort(arr,0,length);
        Permulation(arr,0,length);
    }
    return 0;
}
void Permulation(char *arr,int k,int length){
    int i;
    if(k == length){
        for(i=0;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+1,length);
            Permulation(arr,k+1,length);
            bubbleSort(arr,k+1,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+1;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
****************************************************************/