【問題】(C語言) [遞迴]字串中所有字元的排列可能

[~雨豆阿底．一人房~ 10]

我想請問的是：

以C語言將一個字串中所有字元可能的排序印出，(最大8字元)

如：若輸入ADY

就輸出ADY、AYD、DAY、DYA、等六種可能。

以下是我的程式碼：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 9

void show_permutation(const char s[], char prefix[]);

int main(void)
{
    int i, j, n=0;
    char word[SIZE], zero[SIZE];
    for(i=0;i<SIZE-1;i++)
       word[i]=zero[i]=0;
    word[i]=zero[i]='\0';

    printf("The max length of the string is 8. (and no dup characters)\n");
    printf("Put in the string to permutate:");
    scanf("%s", &word);

    show_permutation(word, zero);

    system("pause");   
    return 0;
}

void show_permutation(const char s[], char prefix[])
{
    int i, j;


    for(i=0;i<strlen(s);i++){
       //printf("%c", s[i]);
       for(j=0;j<SIZE-1;j++){
          if(prefix[j]==0){
             prefix[j]=s[i];
             break;
          }
       }

       int k=0;
       char copy[strlen(s)];
       for(j=0;j<SIZE-1;j++)
          copy[j]=0;
       copy[j]='\0';


       for(j=0;j<strlen(s);j++){
          if(j!=i){
             copy[k++]=s[j];
          }                   
       }


//       printf(" %s\n", copy);
       show_permutation(copy, prefix);

    }
    if(strlen(s)==0){
       printf("%s\n", prefix);      
       for(i=0;i<SIZE-1;i++)
          prefix[i]=0;
       prefix[i]='\0';
    }

    return ;
}

概念是將s字串中的字元一個一個移動到prefix字串中，

當s字串長度=0時，就將prefix印出。

我上網找時有看到這裡有同樣的題目和相似的想法、

但我怎麼試就是不成功。

請問我的程式碼該如何修改、會較貼近我的想法呢?

(我知道我最後一段的prefix清空有很大的問題...可是不清空他會一直跑出陣列範圍...)

[TerryW 10]

的確prefix不該在最後清空

他應該在每次從遞回出來時清除最後面的字元

這樣才能再從後面加新的字元

btw

字元陣列的初始化不用這麼麻煩

只要char s="";就行了

[j100002ben 10]

概念是將s字串中的字元一個一個移動到prefix字串中，

當s字串長度=0時，就將prefix印出。

我是覺得這樣的演算法會比較麻煩，相對的程式操作上也會比較複雜與辛苦。

而且還會浪費一些記憶體在宣告cpoy的部分。

我是建議：

先開一個flag陣列，儲存這個字元有沒有被儲存過。

當然都要先設定為0。

一個for回圈，跑出一個字元，然後遞迴跑出下一個字元

直到已產生的字元和原始字串長度相等，

輸出，回到上一層。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define SIZE 9

void show_permutation(const char * const w,char * const o,int len,bool * const f,int l);
int main(void)
{
    char word[SIZE],output[SIZE];
    //↑宣告字元陣列
    bool flag[SIZE-1]={false};
    //↑宣告flag並設定為0
    memset(word,0,SIZE);
    memset(output,0,SIZE);
    //↑字串初始化為NULL字元 
    printf("The max length of the string is 8. (and no dup characters)\n");
    printf("Put in the string to permutate:");
    //↑輸出訊息 
    fgets(word,SIZE-1,stdin);
    //↑抓取字串
    word[strlen(word)-1]=word[strlen(word)-1]=='\n'?0:word[strlen(word)-1];
    //↑移除字串結尾的\n
    show_permutation(word,output,strlen(word),flag,0);
    //↑排列組合(遞迴) 
    system("pause");
    //↑程式暫停 
    return 0;
    //↑程式結束 
}

void show_permutation(const char * const w,char * const o,int len,bool * const f,int l)
{
    int i;
    //↑迴圈變數 
    if(l>=len){
       //↑OUTPUT字串與原字串長度相等 
       printf("%s\n",o);
       //↑輸出 
       return;
       //↑結束，回上一層 
       }
    for(i=0;i<len;i++)
        //↑找出一個字元 
        if(!f[i]){
           //↑該字元沒有用過 
           o[l]=w[i];
           //↑複製到OUTPUT字串 
           f[i]=true;
           //↑設定該字元已用過 
           show_permutation(w,o,len,f,l+1);
           //↑跑下一個字元 
           f[i]=false;
           //↑設定該字元未用過 
           }
    o[l]=0;
    //↑OUTPUT設定為NULL 
    return;
    //↑遞迴結束 
}

另外，對於CHAR變數來說

'\0'

和

0

是一樣的，都代表NULL字元

恕刪

字元陣列的初始化不用這麼麻煩

只要char s="";就行了

不過編譯器會怎麼處理字串又是另一回事

有些會將全部的字串設定成NULL字元，有些只在第一個設定NULL字元。

這就像下面三個函數的差別吧～一_一狠

memset

memcpy

strcpy

[TerryW 10]

不過編譯器會怎麼處理字串又是另一回事

有些會將全部的字串設定成NULL字元，有些只在第一個設定NULL字元。

這就像下面三個函數的差別吧～

只要在一開始宣告陣列時初始化，後面未被指定內容的元素會隱含的初始化為0

像是下面這些：

int ia[10]={0};

float fa[10]={1.0f, 2.0f};

char cha[10]={0};

恩，不過真要說的話我並不是很確定

char cha[10]="";和char cha[10]={0};是否同義就是

就我目前用到現在都是這樣啦(汗)

[j100002ben 10]

只要在一開始宣告陣列時初始化，後面未被指定內容的元素會隱含的初始化為0

像是下面這些：

int ia[10]={0};

float fa[10]={1.0f, 2.0f};

char cha[10]={0};

恩，不過真要說的話我並不是很確定

char cha[10]="";和char cha[10]={0};是否同義就是

就我目前用到現在都是這樣啦(汗)

所以我喜歡用memset()

函式原型：

#include <string.h>
extern void *memset(void *buffer, int c, int count);

將buffer中count長度的記憶體設為c

[jo35k6 10]

貌似

char cha[10];

就已經都是 Null了..

[j100002ben 10]

貌似

char cha[10];

就已經都是 Null了..

沒有唷....

那只是宣告了10個記憶體位置....一_一狠