剣指OFFERの文字列の並び(九度OJ 1369)

タイトルの説明:
 
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列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

問題解決の考え方:
この問題は2つの問題に注意しなければならない.
1つ目は繰り返しアルファベットで、2つ目は辞書順です.
アルファベットを繰り返して交換するときは直接スキップすればいいので、辞書の順番で並べていく必要があります.
配列はバブルソートを使用します.

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("
");

    }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("
");

    }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

****************************************************************/