全配列と辞書配列
まず、全配列は比較的簡単な問題ですが、私は本当に全配列を実現したことがありません.
私一人で全配列を考えさせると、「abcd」を全配列にすると、このような簡単な全配列も私を困らせることができます.本当にこのような問題を考えたことがないからです.しばらく考えてみると、私は以下の面倒なアルゴリズムしか与えられません.
実はここ数日多く多くのアルゴリズムの多くの構想を見た後で、かえって1種の解題方法を知らないで完全に考えない状態に陥って、ああ、頭が悪くなってしまいました.
ここでより簡単な考え方は、全配列は1番目のアルファベットから始まり、その後のアルファベットと交換し、再帰的な出力はすべて:
これは再帰的な方法です.
非再帰的に一般的には、文字列の全配列は、辞書シーケンス配列を使用して実現することができる.
ここで辞書の順序のアルゴリズムはとても面白いので、覚えておいてください.
ディクショナリシーケンスのソートを行う文字列strについては、右側の要素よりも小さい最初の点str[i]を右から探します.次に、iから文字列の最後にstr[i]より大きい最小文字str[j]を探し、str[i]とstr[j]を交換する.iの後のサブストリングを逆さまにして,新しい辞書順ソートの結果を得た.その後、この結果に基づいて次のソートを探します.このアルゴリズムはとてもおもしろくて、このような精緻な構想はどのように発生して、私は知ることができなくて、しかし私はこのようにする意図を理解しました.まず、最初の文字列はソートされたディクショナリシーケンスの開始状態であり、その後、ループの開始ごとに文字列を2つのセグメントに分け、左側はディクショナリソートされていないサブセグメントであり、右側はディクショナリソートされたサブセグメントであり、このサブセグメントの前のディクショナリシーケンスはすでに遍歴され出力されており、ここでは最初の右側より小さい要素str[i]を探し、この順序より前のディクショナリ順序が出力されている場合、右側のフィールドは必ず大きいから小さいまで並べ替えられ、右側のサブセグメントのディクショナリ順序もすべて出力される.これはstr[i]の前と自身を含めてすべて遍歴している場合、str[i]をより大きな要素に変えて並べ替えることを示している.この数は、右フィールドのstr[i]より大きい最小要素str[j]であり、str[i]とstr[j]を交換し、str[j]で始まる新しい辞書シーケンスを遍歴し、このとき右フィールドを逆転させる.これは、以前は大きいものから小さいものまで並べ替えられていたためであり、交換後は小さいものから大きいものまで並べ替えられていたが、これはstr[j]が開始時であり、右サブセグメントの最初の辞書シーケンスである.このように繰り返してすべての辞書順を出力します.
次に、辞書順に並べられたコードを簡単に書きます.
私一人で全配列を考えさせると、「abcd」を全配列にすると、このような簡単な全配列も私を困らせることができます.本当にこのような問題を考えたことがないからです.しばらく考えてみると、私は以下の面倒なアルゴリズムしか与えられません.
//
void printRE(char* str,int index,char s[],int length){
if(index == length)
printf("%s
",str);
else{
bool exsist = false;
for(int i = 0 ; i < length;i++){
exsist = false;
for(int j= 0; j < index;j++){
if(s[i] == str[j]){
exsist = true;
break;
}
}
if(!exsist){
str[index] = s[i];
printRE(str,index+1,s,length);
}
}
}
}
void PrintAll(char s[],int length){
char* str = new char[length+1];
str[length] = '\0';
printRE(str,0,s,length);
delete[] str;
}
ここでは、スタックとして使用するために文字列配列strを使用し、再帰的な遡及を実現する.ここで、文字が使用されたかどうかの判断は、スタック内の要素を遍歴し、前の部分の文字列にいくつかの文字が使用されているかどうかを見ることです.実はここ数日多く多くのアルゴリズムの多くの構想を見た後で、かえって1種の解題方法を知らないで完全に考えない状態に陥って、ああ、頭が悪くなってしまいました.
ここでより簡単な考え方は、全配列は1番目のアルファベットから始まり、その後のアルファベットと交換し、再帰的な出力はすべて:
void printALLA(char* str,char *begin){
if('\0' == *begin)
printf("%s
",str);
else{
for(char* p = begin;*p != '\0';p++){
swap(*p,*begin);
printALLA(str,begin+1);
swap(*p,*begin);// 。
}
}
}
これは再帰的な方法です.
非再帰的に一般的には、文字列の全配列は、辞書シーケンス配列を使用して実現することができる.
ここで辞書の順序のアルゴリズムはとても面白いので、覚えておいてください.
ディクショナリシーケンスのソートを行う文字列strについては、右側の要素よりも小さい最初の点str[i]を右から探します.次に、iから文字列の最後にstr[i]より大きい最小文字str[j]を探し、str[i]とstr[j]を交換する.iの後のサブストリングを逆さまにして,新しい辞書順ソートの結果を得た.その後、この結果に基づいて次のソートを探します.このアルゴリズムはとてもおもしろくて、このような精緻な構想はどのように発生して、私は知ることができなくて、しかし私はこのようにする意図を理解しました.まず、最初の文字列はソートされたディクショナリシーケンスの開始状態であり、その後、ループの開始ごとに文字列を2つのセグメントに分け、左側はディクショナリソートされていないサブセグメントであり、右側はディクショナリソートされたサブセグメントであり、このサブセグメントの前のディクショナリシーケンスはすでに遍歴され出力されており、ここでは最初の右側より小さい要素str[i]を探し、この順序より前のディクショナリ順序が出力されている場合、右側のフィールドは必ず大きいから小さいまで並べ替えられ、右側のサブセグメントのディクショナリ順序もすべて出力される.これはstr[i]の前と自身を含めてすべて遍歴している場合、str[i]をより大きな要素に変えて並べ替えることを示している.この数は、右フィールドのstr[i]より大きい最小要素str[j]であり、str[i]とstr[j]を交換し、str[j]で始まる新しい辞書シーケンスを遍歴し、このとき右フィールドを逆転させる.これは、以前は大きいものから小さいものまで並べ替えられていたためであり、交換後は小さいものから大きいものまで並べ替えられていたが、これはstr[j]が開始時であり、右サブセグメントの最初の辞書シーケンスである.このように繰り返してすべての辞書順を出力します.
次に、辞書順に並べられたコードを簡単に書きます.
void printLexOrder(char s[],int length){
int charBarrel[128];
memset(charBarrel,0,128*4);
for(int i = 0 ; i < length;i++){
charBarrel[ s[i] ] ++;
}
int i,j;
i = 0;
char* str = new char[length+1];
str[length] = '\0';
for(j = 0 ; j < 128;j++){
while(charBarrel[j] > 0){
charBarrel[j]--;
str[i++] = j;
}
}
int min;// i
char* stack = new char[length];
int stacktop = 0;//
printf("%s
",str);
while(i > -1){
j = length-1;
i = j - 1;
while(str[i] >= str[j]){
i--;
j--;
if(i<0)
break;
}
if(i<0)break;//
j = i+1;
min = j;
while(j<length){
if(str[j] > str[i] && str[j] <= str[min]){
min = j;
}
j++;
}
j = min;
stack[stacktop] = str[i];
str[i] = str[j];
str[j] = stack[stacktop];
for(j = i+1;j<length;j++)
stack[stacktop++] = str[j];
while(stacktop > 0)
str[++i] = stack[--stacktop];
printf("%s
",str);
}
delete[] stack, str;
}