字符串的全排列（数组方式）

谁借莪１个温暖的怀抱￠ 2022-05-30 11:08 140阅读 0赞

全排列图解过程

![SouthEast][]

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    void dg(char str[],int k){
         
         
         if(k==strlen(str)-1){
         
             for(int j=0;j<=k;j++){
                     printf("%c",str[j]);
             }
             printf("\n");
             return ;
         }
         //没有重复字符的全排列 
         /*for(int i=k;i<strlen(str);i++){
             char temp=str[k];
             str[k]=str[i];
             str[i]=temp;
             dg(str,k+1);
             temp=str[k];
             str[k]=str[i];
             str[i]=temp;
         }  */
         //有重复字符的全排列 
         //因为全排列是将不同元素依次换到当前位置后，再对后面的元素求全排列。
         //如果将重复的元素多次换到当前位置的话，那么就会出现相同的排列。
         //为了避免，我们禁止将相同的元素多次换到当前位置即可
         //这样我们也得到了在全排列中去掉重复的规则：去重的全排列就是
         //从第一个数字起每个数分别与它后面非重复出现的数字交换。   
         for(int i=k;i<strlen(str);i++){
             int t=i,ok=0;
             for(int j=t+1;j<strlen(str);j++){
             if(str[t]==str[j])
                 ok=1;
             }
             if(!ok){
             char temp=str[k];
             str[k]=str[i];
             str[i]=temp;
             dg(str,k+1);
             temp=str[k];
             str[k]=str[i];
             str[i]=temp;
             }
         }     
    }
    int main(){
        char s[]={'A','B','C'},s1[]={'A','B','B'};
        //dg(s,0);
        dg(s1,0);
        system("pause");
        return 0;
    }

[SouthEast]: /images/20220530/9c8dd84a1bfb46da824b2447124dcccb.png