【投稿】文字列の配列

スレッド:http://zhedahht.blog.163.com/blog/static/254111742007499363479/
    タイトル：文字列を入力して、文字列の中の文字のすべての配列を印刷して、文字列a b cのようです。文字列a、b、cで並べられる文字列abc、acb、bac、bca、cabとcbaを出力します。
    分析：これはとてもいい試験問題です。再帰的に理解するためのプログラミング問題です。この一年の間に、各大手会社の面接、筆記試験問題に頻繁に現れました。
    3つの文字abcを例にとって、文字列の配列を求める過程を分析します。まず最初の文字aを固定して、後の2つの文字bcの配置を求めます。2つの文字bcの配列がよくなったら、最初の文字aと後ろのbを交換して、b acを得て、次に最初の文字bを固定して、後の2つの文字acの配列を求めます。今はcを第一の位置に置く時です。前の文字を覚えてください。最初の文字aと後ろのbを交換しました。今回のcは元の位置にあるaと交換することを保証するために、cと最初の文字を交換する前に、bとaを交換して帰ります。bとaを交換した後、cと第一の位置にあるaを持って交換して、cbaをもらいます。最初の文字cを再度固定して、後の二文字のb、aの配列を求めます。
    三文字の並びをどう求めるかはすでに分かりましたが、最初の文字を固定してから後の二文字の並びを求めるのが典型的な再帰的な考え方です。前の分析に基づいて、下記の参照コードを得ることができます。

 1 void Permutation(char* pStr, char* pBegin);  //    
 2 
 3 /////////////////////////////////////////////////////////////////////////
 4 // Get the permutation of a string,
 5 // for example, input string abc, its permutation is
 6 // abc acb bac bca cba cab
 7 /////////////////////////////////////////////////////////////////////////
 8 void Permutation(char* pStr)
 9 {
10       Permutation(pStr, pStr);
11 }
12 
13 /////////////////////////////////////////////////////////////////////////
14 // Print the permutation of a string,
15 // Input: pStr   - input string
16 //        pBegin - points to the begin char of string
17 //                 which we want to permutate in this recursion
18 /////////////////////////////////////////////////////////////////////////
19 void Permutation(char* pStr, char* pBegin)
20 {
21       if(!pStr || !pBegin) return;
22 
23       // if pBegin points to the end of string,
24       // this round of permutation is finished, 
25       // print the permuted string
26       if(*pBegin == '\0') {
27             printf("%s
", pStr);
28       }
29       // otherwise, permute string
30       else {
31             for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
32             {
33                   // swap pCh and pBegin
34                   char temp = *pCh;
35                   *pCh = *pBegin;
36                   *pBegin = temp;
37 
38                   Permutation(pStr, pBegin + 1);
39 
40                   // restore pCh and pBegin
41                   temp = *pCh;
42                   *pCh = *pBegin;
43                   *pBegin = temp;
44             }
45       }
46 }

void my_permutation(char *str, int len, int index)
{
    if (str == NULL) return;
    if (index == len) cout << str << endl;
    for (int i = index; i < len; i++) {
        SWAP(str[i], str[index]);
        my_permutation(str, len, index+1);
        SWAP(str[i], str[index]);
    }
}

    拡張1：文字のすべての配列を求めるのではなく、文字のすべての組み合わせを求めるなら、どうすればいいですか？入力した文字列に同じ文字列が含まれている場合、同じ文字の交換位置は異なる配列ですが、同じ組み合わせです。例えば、a b cを入力すると、その組み合わせはa、b、c、ab、ac、bc、abcがあります。
    拡張2：8つの数字を含む配列を入力して、この8つの数字をそれぞれ正方体の8つの頂点に置くことができるかどうかを判断します。正方体上の3つの組の相対的な面の4つの頂点の和が等しいです。
————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
    八皇后問題
    テーマ：8にあります×8のチェスの上で8つの皇后を並べて、それにお互いに攻撃することができないようにして、つまりいかなる2つの皇后は同一の行、同一の列あるいは同一の対角線の上にいてはいけなくて、全部でどれだけの種類の振り子がありますか？
    8つの皇后のいずれかの2つは同じ行にあることができません。つまり、各皇后が一行を占めています。1つの配列ColumnIndex[8]を定義できます。配列の中でi番目の数字はi行目の皇后の列番号を表します。まずColumnIndexの8つの数字をそれぞれ0-7で初期化します。次に私達がやるべきことは配列ColumnIndexに対して全配列をすることです。私たちは異なる数字で配列の中の数字を初期化しますので、どちらかの2つの皇后はきっと違う列になります。私たちは、得られた各配列に対応する8つの皇后が同一の対角線上にあるかどうか、つまり配列の2つの下付きiとjであり、i-j=ColumnIndex[i]-Column[j]またはj-i==ColumnIndex[i]-ColumnIndex[j]ではないかを判断する必要があります。

int g_number = 0;

void EightQueen()
{
    const int queens = 8;
    int ColumnIndex[queens];
    for(int i = 0; i < queens; ++ i)
        ColumnIndex[i] = i;
    Permutation(ColumnIndex, queens, 0);
}

void Permutation(int ColumnIndex[], int length, int index)
{
    if(index == length) {
        if(Check(ColumnIndex, length)) {
            ++ g_number;
            PrintQueen(ColumnIndex, length);
        }
    }
    else {
        for(int i = index; i < length; ++ i) {
            SWAP(ColumnIndex[i], ColumnIndex[index]);
            Permutation(ColumnIndex, length, index + 1);
            SWAP(ColumnIndex[i], ColumnIndex[index]);
        }
    }
}

bool Check(int ColumnIndex[], int length) //           
{
    for(int i = 0; i < length; ++ i) {
        for(int j = i + 1; j < length; ++ j) {
            if((i - j == ColumnIndex[i] - ColumnIndex[j])
                || (j - i == ColumnIndex[i] - ColumnIndex[j]))
                return false;
        }
    }
    return true;
}

void PrintQueen(int ColumnIndex[], int length)
{
    printf("Solution %d
", g_number);
    for(int i = 0; i < length; ++i)
        cout << ColumnIndex[i] << " ";
    cout << endl;
}

    複雑ですが、脈絡がはっきりしています。