簡単な再帰的な考え方とC++の実現を並べて組み合わせる

本稿では,再帰的な方法で全配列と組合せを実現する方法を説明し,再帰的な考え方を詳細に説明し,最後にc++実現のソースコードも与える.以前はデータ構造とアルゴリズムを勉強していたとき、それらの再帰的な考え方が分からなかったが、今日出会って、よく考えてみると、以前ほど難しくないことに気づいたので、コードを下ろして、同時に考えをメモした.
整列
まず配列:例えばA B C Dの4文字の全配列は以下の24種類です

ABCD, ABDC, ACDB, ACBD, ADBC, ADCB, BCDA, BCAD, BDAC, BDCA, BACD, BADC, CDAB, CDBA, CABD, CADB, CBDA, CBAD, DABC, DACB, DBCA, DBAC, DCAB, DCBA

すべての配列が必要なアルファベットがn個(R 1,R 2...Rn)あると仮定し、後(n-1)個のアルファベットがすでに全配列(Rmは後n-1個のアルファベットを表す)であれば(R 0,Rm)、(R 1,Rm)...(Rn,Rm)は全配列であり、RiはRmに含まれない.つまり、まず後ろのn-1文字を全部並べて、それからすべてのn個を並べて、どのようにn個を並べますか?すべてのアルファベットを順番に最初の位置に並べます.このようにして、後n−1個を全配列する前に、後n−2個、、、n個目まで全配列する.これが再帰的な考え方です.

#include 
#include 

using namespace std;

/*
   
*/
class TotalOrdering {
    //       
    vector<char> letters = { 'A', 'B', 'C', 'D' };
    vector<string> result;//    

public:

    /*
      ：
    start              ，      0，   ，                （0, letters.size()-1）
    str       
    */
    void order(int start, string str) {
        if (start >= letters.size()) {//        ，    
            result.push_back(str);
            return;
        }

        for (int i = start; i < letters.size(); ++i) {//               
            order(start + 1, str + letters[start]);
            forward(letters, start);
        }
    }

    //              ，          
    //     abcd,          bcda
    void forward(vector<char> &letters, int start) {
        if (start >= letters.size() - 1)return;

        char first = letters[start];
        int i = start + 1;
        for (; i < letters.size(); ++i) {
            letters[i - 1] = letters[i];
        }
        letters[i - 1] = first;
    }

    void print() {
        auto begin = result.begin();
        for (; begin != result.end(); ++begin) {
            string tempStr = *begin;

            cout << tempStr.c_str() << ", ";
        }
    }
};

int main() {
    TotalOrdering totalOrdering;
    totalOrdering.order(0, "");
    totalOrdering.print();

    system("pause");
    return 0;
}

コンポジット
現在、3つの集合{A,B},{C,D},{E,F}があり、3つの集合のすべての要素の組み合わせはACE,ACF,ADE,ADF,BCE,BCF,BDE,BDFの8種類である.後の2つの集合のすべての要素が既に組み合わせられている場合(これらの組合せはRと記す)、同時にRiが最初の集合の要素を表す場合、{Ri,R}(iが(1...nに属する)はすべての組合せである.すなわち{(R 1,R),(R 2,R)…(R 3,R)}はすべての組合せである.これが再帰的な考え方です.これに基づいて、次のコードが実装されます.

#include 
#include 
#include 

using namespace std;

class Solution0017 {
public:
    const string keyboard[10] = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    //       
    vector<string> result;
    vector<string> letterCombinations(string digits) {
        if (digits == "") return vector<string>();

        combine(0, digits, "");
        return result;
    }

    void combine(int size, string & digits, string str) {
        if (size >= digits.length()) {
            result.push_back(str);
            return;
        }
        string letters = keyboard[digits[size] - '0'];
        for (int i = 0; i < letters.length(); ++i) {
        //                   ，        “  ”
            combine(size + 1, digits, str + letters[i]);
        }
    }


};


int main() {

    Solution0017 solution;
    //      {a,b,c},       {d,e,f}
    vector<string> result = solution.letterCombinations("23");
    cout << result.size() << endl;

    system("pause");
    return 0;
}

この例もleetcodeの17番目のアルゴリズム問題の答えです.
ようこそ!